2026-07-26T03:02:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12419 2024-03-06T10:50:05Z ddc:004 open_access

Improved Bounds for Matching in Random-Order Streams Bernstein, Aaron Graph Algorithms Sublinear Algorithms Matching Streaming We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, the edges of the input graph G = (V,E) are given as a stream e₁, …, e_m, and the algorithm is allowed to make a single pass over this stream while using O(n polylog(n)) space (m = |E| and n = |V|). If the order of edges is adversarial, a simple single-pass greedy algorithm yields a 1/2-approximation in O(n) space; achieving a better approximation in adversarial streams remains an elusive open question. A line of recent work shows that one can improve upon the 1/2-approximation if the edges of the stream arrive in a random order. The state of the art for this model is two-fold: Assadi et al. [SODA 2019] show how to compute a 2/3(∼.66)-approximate matching, but the space requirement is O(n^1.5 polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(n polylog(n)), but a worse approximation ratio of 6/11(∼.545), or 3/5(=.6) in bipartite graphs. In this paper, we present an algorithm that computes a 2/3(∼.66)-approximate matching using only O(n log(n)) space, improving upon both results above. We also note that for adversarial streams, a lower bound of Kapralov [SODA 2013] shows that any algorithm that achieves a 1-1/e(∼.63)-approximation requires (n^{1+Ω(1/log log(n))}) space. Our result for random-order streams is the first to go beyond the adversarial-order lower bound, thus establishing that computing a maximum matching is provably easier in random-order streams. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron Bernstein 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.12 urn:nbn:de:0030-drops-124194 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode