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

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

 pdf-format:

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 | Privacy