A simple augmentation method for matchings with applications to streaming algorithms

Christian Konrad*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

6 Citations (Scopus)
35 Downloads (Pure)

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].

Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK
EditorsIgor Potapov, James Worrell, Paul Spirakis
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages74:1-74:16
Number of pages16
ISBN (Print)9783959770866
DOIs
Publication statusPublished - Aug 2018
Event43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom
Duration: 27 Aug 201831 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume117
ISSN (Print)1868-8969

Conference

Conference43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
CountryUnited Kingdom
CityLiverpool
Period27/08/1831/08/18

Keywords

  • Augmenting paths
  • Matchings
  • Random order
  • Streaming algorithms

Fingerprint Dive into the research topics of 'A simple augmentation method for matchings with applications to streaming algorithms'. Together they form a unique fingerprint.

Cite this