License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.74
URN: urn:nbn:de:0030-drops-96560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9656/
Go to the corresponding LIPIcs Volume Portal

Konrad, Christian

A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms

pdf-format:
LIPIcs-MFCS-2018-74.pdf (0.5 MB)

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

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:1--74:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9656},
  URN =		{urn:nbn:de:0030-drops-96560},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI