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  sqrt{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 nvertex graph while maintaining a memory of size O(n polylog n). Our method immediately yields a very simple twopass 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.583approximation 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 onepass random order streaming algorithm for MBM with approximation factor 0.5395. This substantially improves upon the onepass random order 0.505approximation algorithm of Konrad et al. [APPROX 2012].
BibTeX  Entry
@InProceedings{konrad:LIPIcs:2018:9656,
author = {Christian Konrad},
title = {{A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {74:174:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9656},
URN = {urn:nbn:de:0030drops96560},
doi = {10.4230/LIPIcs.MFCS.2018.74},
annote = {Keywords: Matchings, augmenting paths, streaming algorithms, random order}
}
Keywords: 

Matchings, augmenting paths, streaming algorithms, random order 
Collection: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 
Issue Date: 

2018 
Date of publication: 

27.08.2018 