Abstract
We study the problem of computing an approximate maximum cardinality matching in the semistreaming model when edges arrive in a random order. In the semistreaming 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 singlepass greedy algorithm yields a 1/2approximation 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/2approximation if the edges of the stream arrive in a random order. The state of the art for this model is twofold: 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 11/e(∼.63)approximation requires (n^{1+Ω(1/log log(n))}) space. Our result for randomorder streams is the first to go beyond the adversarialorder lower bound, thus establishing that computing a maximum matching is provably easier in randomorder streams.
BibTeX  Entry
@InProceedings{bernstein:LIPIcs:2020:12419,
author = {Aaron Bernstein},
title = {{Improved Bounds for Matching in RandomOrder Streams}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {12:112:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12419},
URN = {urn:nbn:de:0030drops124194},
doi = {10.4230/LIPIcs.ICALP.2020.12},
annote = {Keywords: Graph Algorithms, Sublinear Algorithms, Matching, Streaming}
}
Keywords: 

Graph Algorithms, Sublinear Algorithms, Matching, Streaming 
Collection: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) 
Issue Date: 

2020 
Date of publication: 

29.06.2020 