OASIcs.SOSA.2019.13.pdf
- Filesize: 420 kB
- 8 pages
Document
Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching
Authors
-
Part of:
Volume:
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-01-08
Cite As Get BibTex
Mohsen Ghaffari and David Wajc. Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 13:1-13:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.SOSA.2019.13
Abstract
In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass (2+epsilon)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses O(n log^2 n) bits of space, for any constant epsilon>0. We present a simplified and more intuitive primal-dual analysis, for essentially the same algorithm, which also improves the space complexity to the optimal bound of O(n log n) bits - this is optimal as the output matching requires Omega(n log n) bits.
Subject Classification
Keywords
- Streaming
- Semi-Streaming
- Space-Optimal
- Matching
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. Journal of the ACM (JACM), 48(5):1069-1090, 2001.
-
Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon Even 1935-2004. ACM Computing Surveys (CSUR), 36(4):422-463, 2004.
-
Michael Crouch and Daniel M Stubbs. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 96-104, 2014.
-
Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449-467, 1965.
-
Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics, 25(3):1251-1265, 2011.
-
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2):207-216, 2005.
- Mohsen Ghaffari and David Wajc. Simplified and Space-Optimal Semi-Streaming for (2+ε)-Approximate Matching. arXiv preprint, 2018. URL: http://arxiv.org/abs/1701.03730.
-
Andrew McGregor. Finding graph matchings in data streams. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 170-181. Springer, 2005.
-
Ami Paz and Gregory Schwartzman. A (2+ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2153-2161, 2017.