TY - JOUR
T1 - Improved Bounds for Matching in Random-Order Streams
AU - Bernstein, Aaron
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023.
PY - 2024/8
Y1 - 2024/8
N2 - 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 e1,…,em, and the algorithm is allowed to make a single pass over this stream while using O(npolylog(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 23(∼.66)-approximate matching, but the space requirement is O(n1.5polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(npolylog(n)), but a worse approximation ratio of 611(∼.545), or 35(=.6) in bipartite graphs. In this paper, we present an algorithm that computes a 23(∼.66)-approximate matching using only O(nlog(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-1e(∼.63)-approximation requires (n1+Ω(1/loglog(n))) space; recent follow-up work by the same author improved this lower bound to 1+ln(2)∼.59 [SODA 2021]. As a consequence, both our result and the earlier result of Farhadi et al. prove that the problem of computing a maximum matching is strictly easier in random-order streams than in adversarial ones.
AB - 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 e1,…,em, and the algorithm is allowed to make a single pass over this stream while using O(npolylog(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 23(∼.66)-approximate matching, but the space requirement is O(n1.5polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(npolylog(n)), but a worse approximation ratio of 611(∼.545), or 35(=.6) in bipartite graphs. In this paper, we present an algorithm that computes a 23(∼.66)-approximate matching using only O(nlog(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-1e(∼.63)-approximation requires (n1+Ω(1/loglog(n))) space; recent follow-up work by the same author improved this lower bound to 1+ln(2)∼.59 [SODA 2021]. As a consequence, both our result and the earlier result of Farhadi et al. prove that the problem of computing a maximum matching is strictly easier in random-order streams than in adversarial ones.
KW - Matching
KW - Random-Order
KW - Streaming
UR - http://www.scopus.com/inward/record.url?scp=85179373468&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85179373468&partnerID=8YFLogxK
U2 - 10.1007/s00224-023-10155-7
DO - 10.1007/s00224-023-10155-7
M3 - Article
AN - SCOPUS:85179373468
SN - 1432-4350
VL - 68
SP - 758
EP - 772
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 4
ER -