License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.15
URN: urn:nbn:de:0030-drops-75645
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7564/
Go to the corresponding LIPIcs Volume Portal


Kale, Sagar ; Tirodkar, Sumedh

Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

pdf-format:
LIPIcs-APPROX-RANDOM-2017-15.pdf (0.6 MB)


Abstract

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu. In three passes, we achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely - we give a (2/3 - epsilon)-approximation algorithm that uses 2/(3 epsilon) passes for triangle-free graphs and 4/(3 epsilon) passes for general graphs. Our algorithms are simple and combinatorial, use O(n log(n)) space, and have O(1) update time per edge. For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes: * Ahn and Guha give a (2/3 - epsilon)-approximation algorithm that uses O(log(1/epsilon)/epsilon^2) passes, whereas our (2/3 - epsilon)-approximation algorithm uses 4/(epsilon) passes; * they also give a (1 - epsilon)-approximation algorithm that uses O(log(n) poly(1/epsilon)) passes, where n is the number of vertices of the input graph; although our algorithm is (2/3 - epsilon)-approximation, our number of passes do not depend on n. Earlier multi-pass algorithms either have a large constant inside big-O notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below 2/3.

BibTeX - Entry

@InProceedings{kale_et_al:LIPIcs:2017:7564,
  author =	{Sagar Kale and Sumedh Tirodkar},
  title =	{{Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{15:1--15:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7564},
  URN =		{urn:nbn:de:0030-drops-75645},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.15},
  annote =	{Keywords: Semi Streaming, Maximum Matching}
}

Keywords: Semi Streaming, Maximum Matching
Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 31.07.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI