Document Open Access Logo

Beating Two-Thirds For Random-Order Streaming Matching

Authors Sepehr Assadi, Soheil Behnezhad

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.19.pdf
  • Filesize: 1.33 MB
  • 13 pages

Document Identifiers

Author Details

Sepehr Assadi
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA
Soheil Behnezhad
  • Department of Computer Science, University of Maryland, College Park, MD, USA

Funding

  • Assadi, Sepehr: Research supported in part by the NSF CAREER award CCF-2047061 and a gift from Google Research.
  • Behnezhad, Soheil: Research supported by Google Ph.D. Fellowship.

Acknowledgements

We thank Aaron Bernstein for helpful conversations on the random-order streaming matching problem and several insightful comments that helped us in improving the presentation of the paper. We also thank the anonymous ICALP reviewers for their valuable comments.

Cite AsGet BibTex

Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.19

Abstract

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary n-vertex graph G = (V, E) arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use O(n ⋅ polylog) space, and output a large matching of G. We prove that for an absolute constant ε₀ > 0, one can find a (2/3 + ε₀)-approximate maximum matching of G using O(n log n) space with high probability. This breaks the natural boundary of 2/3 for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a (2/3 + Ω(1))-approximation is achievable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Maximum Matching
  • Streaming
  • Random-Order Streaming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1616-1635, 2019. Google Scholar
  2. Sepehr Assadi and Soheil Behnezhad. Beating two-thirds for random-order streaming matching. CoRR, abs/2102.07011, 2021. URL: http://arxiv.org/abs/2102.07011.
  3. Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8-9, 2019 - San Diego, CA, USA, pages 11:1-11:20, 2019. Google Scholar
  4. Claude Berge. The theory of graphs. Courier Corporation, 1962. Google Scholar
  5. Aaron Bernstein. Improved bounds for matching in random-order streams. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 12:1-12:13, 2020. Google Scholar
  6. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, July 6-10, 2015, Proceedings, Part I, pages 167-179, 2015. Google Scholar
  7. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, January 10-12, 2016, pages 692-711, 2016. Google Scholar
  8. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi. Approximate maximum matching in random streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1773-1785, 2020. Google Scholar
  9. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. Google Scholar
  10. Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. Weighted matchings via unweighted augmentations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 491-500, 2019. Google Scholar
  11. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 468-485. SIAM, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095157.
  12. Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, 1(1):26-30, 1935. Google Scholar
  13. Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1679-1697, 2013. URL: https://doi.org/10.1137/1.9781611973105.121.
  14. Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2021. Google Scholar
  15. Christian Konrad. A simple augmentation method for matchings with applications to streaming algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 74:1-74:16, 2018. Google Scholar
  16. Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 231-242, 2012. Google Scholar
  17. William T Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 1(2):107-111, 1947. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact