Beating two-thirds for random-order streaming matching

Sepehr Assadi, Soheil Behnezhad

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary n-vertex graph G = (V,E) arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use O(n · polylog(n)) space, and output a large matching of G. We prove that for an absolute constant ∈0 > 0, one can find a (2/3 + ∈0)-approximate maximum matching of G using O(n log n) space with high probability. This breaks the natural boundary of 2/3 for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a (2/3 + Ω(1))-approximation is achievable.

Original languageEnglish (US)
Title of host publication48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
EditorsNikhil Bansal, Emanuela Merelli, James Worrell
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771955
DOIs
StatePublished - Jul 1 2021
Event48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 - Virtual, Glasgow, United Kingdom
Duration: Jul 12 2021Jul 16 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume198

Conference

Conference48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Country/TerritoryUnited Kingdom
CityVirtual, Glasgow
Period7/12/217/16/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Maximum Matching
  • Random-Order Streaming
  • Streaming

Cite this