プログラミング
単一パス半ストリーミングマッチングにおける貪欲法の最適性
Greedy is optimal for single-pass semi-streaming matching (arxiv.org)
要約
本論文では、最大マッチング問題に対する単一パス半ストリーミングアルゴリズム（決定論的または確率論的）が、半分の近似値を超える性能を達成できないことを証明しています。これは、20年以上前にモデルが導入されて以来、グラフストリーミング分野で未解決だった問題に対する、単純な貪欲アルゴリズムの最適性を確立するものです。この結果は、プリエンプションを伴うオンラインマッチングの最適な競争比が半分であるという、同様に未解決だった問題も解決します。
全文翻訳
単一パス半ストリーミングマッチングII: 貪欲法は最適である
著者: Sepehr Assadi, Max Jiang, Mars Xiang
我々は、いかなる単一パス半ストリーミングアルゴリズム（決定論的または確率論的）も、最大マッチング問題に対して半分の近似値よりも良い性能を達成できないことを証明する。
これは、20年以上前にモデルが導入されて以来、グラフストリーミングの文献における未解決の疑問に対する、単純な貪欲アルゴリズムの最適性を示唆する。
我々の証明は、著者らによって以前に導入された「ブループリントフレームワーク」に従う。このフレームワークは、半ストリーミングマッチングの下界の証明を、ブループリントと呼ばれる特定の組み合わせオブジェクトの構築に還元する。
我々は、このフレームワークで使用された場合に、我々の半ストリーミングマッチングの下界を示唆する、ブループリントの最適な構築を提示する。
我々の結果はまた、プリエンプションを伴うオンラインマッチングの最適な競争比が半分であり、これもまた単純な貪欲アルゴリズムと一致することを示唆し、この未解決の問題も解決する。
コメント: 23ページ、3図。バージョン2: 全体的に誤字脱字や軽微な言語表現を修正しました。
主題: データ構造とアルゴリズム (cs.DS); 計算複雑性 (cs.CC)