HN 日本語サマリー

← 一覧へ戻る
プログラミング

単一パス半ストリーミングマッチングにおける貪欲法の最適性

Greedy is optimal for single-pass semi-streaming matching (arxiv.org)

10 pointsby MarcoDewey0 コメント

要約

本論文では、最大マッチング問題に対する単一パス半ストリーミングアルゴリズム(決定論的または確率論的)が、半分の近似値を超える性能を達成できないことを証明しています。これは、20年以上前にモデルが導入されて以来、グラフストリーミング分野で未解決だった問題に対する、単純な貪欲アルゴリズムの最適性を確立するものです。この結果は、プリエンプションを伴うオンラインマッチングの最適な競争比が半分であるという、同様に未解決だった問題も解決します。

全文翻訳

Computer Science > Data Structures and Algorithms

arXiv:2607.14656 (cs)

[Submitted on 16 Jul 2026 (v1), last revised 20 Jul 2026 (this version, v2)]

Title:Semi-Streaming Matching in a Single Pass II: Greedy is Optimal

Authors:Sepehr Assadi, Max Jiang, Mars Xiang

View a PDF of the paper titled Semi-Streaming Matching in a Single Pass II: Greedy is Optimal, by Sepehr Assadi and 2 other authors

View PDF HTML (experimental)

Abstract:We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in the graph streaming literature since the introduction of the model over two decades ago.
Our proof follows the "blueprint framework" introduced previously by the authors, which reduced proving lower bounds for semi-streaming matching to constructing certain combinatorial objects called blueprints. We present an optimal construction of blueprints that when used in this framework implies our semi-streaming matching lower bound.
Our results also imply that the optimal competitive ratio of online matching with preemption is half, again matching the naive greedy algorithm, settling this open question as well.

要約:我々は、決定論的または確率論的な単一パス半ストリーミングアルゴリズムでは、最大マッチング問題に対して半分の近似値を超える性能を達成できないことを証明します。これは、ナイーブな貪欲アルゴリズムの最適性を示唆しており、20年以上前にモデルが導入されて以来、グラフストリーミング文献における未解決の重要な問題に答えるものです。
我々の証明は、著者らによって以前に導入された「ブループリントフレームワーク」に従っており、これは半ストリーミングマッチングの下界の証明を、ブループリントと呼ばれる特定の組合せオブジェクトの構築に還元するものです。我々は、このフレームワークで使用された場合に、我々の半ストリーミングマッチングの下界を示唆する、ブループリントの最適な構築を提示します。
我々の結果はまた、プリエンプションを伴うオンラインマッチングの最適な競争比が半分であることを示唆しており、これもナイーブな貪欲アルゴリズムと一致し、この未解決問題も解決します。

Comments:23 pages, 3 figures. Version 2: Fixed typos and minor language issues throughout
Subjects:Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
Cite as:arXiv:2607.14656 [cs.DS]
(or arXiv:2607.14656v2 [cs.DS] for this version)
https://doi.org/10.48550/arXiv.2607.14656 arXiv-issued DOI via DataCite

Submission history

From: Sepehr Assadi
v1 Thu, 16 Jul 2026 07:22:45 UTC (39 KB)
v2 Mon, 20 Jul 2026 02:47:00 UTC (39 KB)

Full-text links:

Access Paper:

View a PDF of the paper titled Semi-Streaming Matching in a Single Pass II: Greedy is Optimal, by Sepehr Assadi and 2 other authors

view license

Additional Features
Current browse context:

cs.DS

< prev   |   next >

new | recent | 2026-07

Change to browse by:

cs
cs.CC

References & Citations

Loading...

BibTeX formatted citation

loading...

Data provided by:

Bookmark

[画像: BibSonomy][画像: Reddit]

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)

Related Papers

Recommenders and Search Tools

Link to Influence Flower

Influence Flower (What are Influence Flowers?)

Core recommender toggle

CORE Recommender (What is CORE?)

  • Author
  • Venue
  • Institution
  • Topic

About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)