LIPIcs.ISAAC.2021.73.pdf
- Filesize: 0.72 MB
- 16 pages
Document
Maximum-Weight Matching in Sliding Windows and Beyond
Authors
-
Part of:
Volume:
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-11-30
Cite As Get BibTex
Leyla Biabani, Mark de Berg, and Morteza Monemizadeh. Maximum-Weight Matching in Sliding Windows and Beyond. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.73
Abstract
We study the maximum-weight matching problem in the sliding-window model. In this model, we are given an adversarially ordered stream of edges of an underlying edge-weighted graph G(V,E), and a parameter L specifying the window size, and we want to maintain an approximation of the maximum-weight matching of the current graph G(t); here G(t) is defined as the subgraph of G consisting of the edges that arrived during the time interval [max(t-L,1),t], where t is the current time. The goal is to do this with Õ(n) space, where n is the number of vertices of G. We present a deterministic (3.5+ε)-approximation algorithm for this problem, thus significantly improving the (6+ε)-approximation algorithm due to Crouch and Stubbs [Michael S. Crouch and Daniel M. Stubbs, 2014]. We also present a generic machinery for approximating subadditve functions in the sliding-window model. A function f is called subadditive if for every disjoint substreams A, B of a stream S it holds that f(AB) ⩽ f(A) + f(B), where AB denotes the concatenation of A and B. We show that given an α-approximation algorithm for a subadditive function f in the insertion-only model we can maintain a (2α+ε)-approximation of f in the sliding-window model. This improves upon recent result Krauthgamer and Reitblat [Robert Krauthgamer and David Reitblat, 2019], who obtained a (2α²+ε)-approximation.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- maximum-weight matching
- sliding-window model
- approximation algorithm
- and subadditve functions
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Aaron Bernstein. Improved bounds for matching in random-order streams. In Proceedings 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of LIPIcs, pages 12:1-12:13, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.12.
- Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In Proceedings 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pages 283-293, 2007. URL: https://doi.org/10.1109/FOCS.2007.55.
- Jiecao Chen, Huy L. Nguyen, and Qin Zhang. Submodular maximization over sliding windows. CoRR, abs/1611.00129, 2016. URL: http://arxiv.org/abs/1611.00129.
- Michael S. Crouch, Andrew McGregor, and Daniel M. Stubbs. Dynamic graphs in the sliding-window model. In Proceedings 21st Annual European Symposium on Algorithms (ESA 2013), volume 8125 of Lecture Notes in Computer Science, pages 337-348. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40450-4_29.
- Michael S. Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, volume 28 of LIPIcs, pages 96-104, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96.
- Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Comput., 31(6):1794-1813, 2002. URL: https://doi.org/10.1137/S0097539701398363.
- Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh. Finding large matchings in semi-streaming. In IEEE International Conference on Data Mining Workshops, ICDM Workshops 2016, pages 608-614, 2016. URL: https://doi.org/10.1109/ICDMW.2016.0092.
- Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi. Approximate maximum matching in random streams. In Proceedings 31st ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1773-1785, 2020. URL: https://doi.org/10.1137/1.9781611975994.108.
- 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. URL: https://doi.org/10.1016/j.tcs.2005.09.013.
- 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, pages 491-500. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331603.
- Mohsen Ghaffari and David Wajc. Simplified and space-optimal semi-streaming (2+epsilon)-approximate matching. In Proceedings 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume 69 of OASICS, pages 13:1-13:8, 2019. URL: https://doi.org/10.4230/OASIcs.SOSA.2019.13.
- Michael Kapralov. Better bounds for matchings in the streaming model. In Sanjeev Khanna, editor, Proceedings 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pages 1679-1697, 2013. URL: https://doi.org/10.1137/1.9781611973105.121.
- 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, volume 7408 of Lecture Notes in Computer Science, pages 231-242, 2012. URL: https://doi.org/10.1007/978-3-642-32512-0_20.
- Robert Krauthgamer and David Reitblat. Almost-smooth histograms and sliding-window graph algorithms. CoRR, abs/1904.07957, 2019. URL: http://arxiv.org/abs/1904.07957.
- Roie Levin and David Wajc. Streaming submodular matching meets the primal-dual method. CoRR, abs/2008.10062, 2020. URL: http://arxiv.org/abs/2008.10062.
-
L. Lovasz and M.D. Plummer. Matching Theory. North-Holland, 1986.
- Silvio Micali and Vijay V. Vazirani. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pages 17-27, 1980. URL: https://doi.org/10.1109/SFCS.1980.12.
- Ami Paz and Gregory Schwartzman. A (2+ε)-approximation for maximum weight matching in the semi-streaming model. In Philip N. Klein, editor, Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2153-2161, 2017. URL: https://doi.org/10.1137/1.9781611974782.140.