@inproceedings{649c8bc5bb3546d693587fa2e815aa20,

title = "A simple augmentation method for matchings with applications to streaming algorithms",

abstract = "Given a graph G, it is well known that any maximal matching M in G is at least half the size of a maximum matching M∗. In this paper, we show that if G is bipartite, then running the Greedy matching algorithm on a sampled subgraph of G produces enough additional edges that can be used to augment M such that the resulting matching is of size at least (2− 2)|M∗| ≈ 0.5857|M∗| (ignoring lower order terms) with high probability. The main applications of our method lie in the area of data streaming algorithms, where an algorithm performs few passes over the edges of an n-vertex graph while maintaining a memory of size O(n polylog n). Our method immediately yields a very simple two-pass algorithm for Maximum Bipartite Matching (MBM) with approximation factor 0.5857, which only runs the Greedy matching algorithm in each pass. This slightly improves on the much more involved 0.583-approximation algorithm of Esfandiari et al. [ICDMW 2016]. To obtain our main result, we combine our method with a residual sparsity property of the random order Greedy algorithm and give a one-pass random order streaming algorithm for MBM with approximation factor 0.5395. This substantially improves upon the one-pass random order 0.505-approximation algorithm of Konrad et al. [APPROX 2012].",

keywords = "Augmenting paths, Matchings, Random order, Streaming algorithms",

author = "Christian Konrad",

year = "2018",

month = aug,

doi = "10.4230/LIPIcs.MFCS.2018.74",

language = "English",

isbn = "9783959770866",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "74:1--74:16",

editor = "Igor Potapov and James Worrell and Paul Spirakis",

booktitle = "43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK",

note = "43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 ; Conference date: 27-08-2018 Through 31-08-2018",

}