単一パス半ストリーミングマッチングにおける貪欲法の最適性
Greedy is optimal for single-pass semi-streaming matching (arxiv.org)
要約
本論文では、最大マッチング問題に対する単一パス半ストリーミングアルゴリズム(決定論的または確率論的)が、半分の近似値を超える性能を達成できないことを証明しています。これは、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
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
Additional Features
Current browse context:
cs.DS
Change to browse by:
References & Citations
Loading...
BibTeX formatted citation
loading...
Data provided by:
Bookmark
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?)