Robust Sparsification for Matroid Intersection with Applications

References

• [1] Assadi S, Behnezhad S (2021) Beating two-thirds for random-order streaming matching. Bansal N, Merelli E, Worrell J, eds. 48th Internat. Colloquium Automata Languages Programming ICALP 2021, LIPIcs, vol. 198 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 19:1–19:13.Google Scholar
• [2] Assadi S, Bernstein A (2019) Towards a unified theory of sparsification for matching problems. Fineman JT, Mitzenmacher M, eds. 2nd Sympos. Simplicity Algorithms SOSA 2019, OASICS, vol. 69 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 11:1–11:20.Google Scholar
• [3] Azarmehr A, Behnezhad S (2023) Robust communication complexity of matching: EDCS achieves 5/6 approximation. Etessami K, Feige U, Puppis G, eds. 50th Internat. Colloquium Automata Languages Programming ICALP 2023, LIPIcs, vol. 261 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 14:1–14:15.Google Scholar
• [4] Behnezhad S, Khanna S (2022) New trade-offs for fully dynamic matching via hierarchical EDCS. Naor JS, Buchbinder N, eds. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms SODA 2022 (SIAM, Philadelphia), 3529–3566.Google Scholar
• [5] Behnezhad S, Roghani M, Rubinstein A (2023) Sublinear time algorithms and complexity of approximate maximum matching. Saha B, Servedio RA, eds. Proc. 55th Annual ACM Sympos. Theory Comput. STOC 2023 (ACM, New York), 267–280.Google Scholar
• [6] Bernstein A (2020) Improved bounds for matching in random-order streams. Czumaj A, Dawar A, Merelli E, eds. 47th Internat. Colloquium Automata Languages Programming ICALP 2020, LIPIcs, vol. 168 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 12:1–12:13.Google Scholar
• [7] Bernstein A, Stein C (2015) Fully dynamic matching in bipartite graphs. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Automata Languages Programming 42nd Internat. Colloquium ICALP 2015 Proc. Part I, Lecture Notes in Computer Science, vol. 9134 (Springer, Berlin), 167–179.Google Scholar
• [8] Bernstein A, Stein C (2016) Faster fully dynamic matchings with small approximation ratios. Krauthgamer R, ed. Proc. Twenty-Seventh Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2016 (SIAM, Philadelphia), 692–711.Google Scholar
• [9] Bhattacharya S, Henzinger M, Italiano G (2018) Dynamic algorithms via the primal-dual method. Inform. Comput. 261(2):219–239.Crossref, Google Scholar
• [10] Bhattacharya S, Kiss P, Saranurak T (2023) Sublinear algorithms for (1.5+ϵ)-approximate matching. Saha B, Servedio RA, eds. Proc. 55th Annual ACM Sympos. Theory Comput. STOC 2023 (ACM, New York), 254–266.Google Scholar
• [11] Blikstad J (2021) Breaking O(nr) for matroid intersection. Bansal N, Merelli E, Worrell J, eds. 48th Internat. Colloquium Automata Languages Programming ICALP 2021, LIPIcs, vol. 198 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 31:1–31:17.Google Scholar
• [12] Blikstad J, Mukhopadhyay S, Nanongkai D, Tu T (2023) Fast algorithms via dynamic-oracle matroids. Preprint, submitted April 27, https://arxiv.org/abs/2302.09796.Google Scholar
• [13] Călinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint (extended abstract). Fischetti M, Williamson DP, eds. Integer Programming Combin. Optim. 12th Internat. IPCO Conf. Proc., Lecture Notes in Computer Science, vol. 4513 (Springer, Berlin), 182–196.Google Scholar
• [14] Chakrabarty D, Lee YT, Sidford A, Singla S, Wong SC (2019) Faster matroid intersection. Zuckerman D, ed. 60th IEEE Annual Sympos. Foundations Comput. Sci. FOCS 2019 (IEEE Computer Society, Washington, DC), 1146–1168.Google Scholar
• [15] Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Automata Languages Programming 42nd Internat. Colloquium ICALP 2015 Proc. Part I, Lecture Notes in Computer Science, vol. 9134 (Springer, Berlin), 318–330.Google Scholar
• [16] Chierichetti F, Kumar R, Lattanzi S, Vassilvitskii S (2019) Matroids, matchings, and fairness. Chaudhuri K, Sugiyama M, eds. 22nd Internat. Conf. Artificial Intelligence Statist. AISTATS 2019, vol. 89 (PMLR, New York), 2212–2220.Google Scholar
• [17] Dougherty R, Freiling C, Zeger K (2011) Network coding and matroid theory. Proc. IEEE 99(3):388–405.Crossref, Google Scholar
• [18] Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy RK, ed. Combin. Structures Applications: Proc. (Gordon and Breach, New York). Google Scholar
• [19] Edmonds J (1971) Matroids and the greedy algorithm. Math. Programming 1(1):127–136.Crossref, Google Scholar
• [20] Edmonds J (1979) Matroid intersection. Hammer PL, Johnson EL, Korte BH, eds. Discrete Optimization I: Proc. Advanced Res. Inst. Discrete Optim. Systems Appl. Systems Sci. Panel NATO Discrete Optim. Sympos., vol. 4 (Elsevier, Amsterdam), 39–49.Crossref, Google Scholar
• [21] Farhadi A, Hajiaghayi MT, Mai T, Rao A, Rossi RA (2020) Approximate maximum matching in random streams. Chawla S, ed. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms SODA 2020 (SIAM, Philadelphia), 1773–1785.Google Scholar
• [22] Feigenbaum J, Kannan S, McGregor A, Suri S, Zhang J (2005) On graph problems in a semi-streaming model. Theoret. Comput. Sci. 348(2–3):207–216.Crossref, Google Scholar
• [23] Feldman M, Karbasi A, Kazemi E (2018) Do less, get more: Streaming submodular maximization with subsampling. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems 31 Annual Conf. Neural Inform. Processing Systems 2018 NeurIPS 2018 (Curran Associates Inc., Red Hook, NY), 730–740.Google Scholar
• [24] Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R (2020) The one-way communication complexity of submodular maximization with applications to streaming and robustness. Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, eds. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. STOC 2020 (ACM, New York), 1363–1374.Google Scholar
• [25] Fujishige S (2008) Theory of principal partitions revisited. Cook WJ, Lovász L, Vygen J, eds. Res. Trends Combin. Optim. Bonn Workshop Combin. Optim. (Springer, Berlin), 127–162.Google Scholar
• [26] Gabow HN, Tarjan RE (1984) Efficient algorithms for a family of matroid intersection problems. J. Algorithms 5(1):80–131.Crossref, Google Scholar
• [27] Gamlath B, Kale S, Mitrovic S, Svensson O (2019) Weighted matchings via unweighted augmentations. Robinson P, Ellen F, eds. Proc. 2019 ACM Sympos. Principles Distributed Comput. PODC 2019 (ACM, New York), 491–500.Google Scholar
• [28] Garg P, Jordan L, Svensson O (2021) Semi-streaming algorithms for submodular matroid intersection. Singh M, Williamson DP, eds. Integer Programming Combin. Optim. 22nd Internat. Conf. IPCO 2021 Proc., Lecture Notes in Computer Science, vol. 12707 (Springer, Cham, Switzerland), 208–222.Google Scholar
• [29] Goel A, Kapralov M, Khanna S (2012) On the communication and streaming complexity of maximum bipartite matching. Rabani Y, ed. Proc. Twenty-Third Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2012 (SIAM, Philadelphia), 468–485.Google Scholar
• [30] Grandoni F, Schwiegelshohn C, Solomon S, Uzrad A (2022) Maintaining an EDCS in general graphs: Simpler, density-sensitive and with worst-case time bounds. Bringmann K, Chan T, eds. 5th Sympos. Simplicity Algorithms SOSA@SODA 2022 (SIAM, Philadelphia), 12–23.Google Scholar
• [31] Gupta M, Peng R (2013) Fully dynamic (1+ε)-approximate matchings. 54th Annual IEEE Sympos. Foundations Comput. Sci. FOCS 2013 (IEEE Computer Society, Washington, DC), 548–557.Google Scholar
• [32] Guruganesh GP, Singla S (2017) Online matroid intersection: Beating half for random arrival. Eisenbrand F, Könemann J, eds. Integer Programming Combin. Optim. 19th Internat. Conf. IPCO 2017 Proc., Lecture Notes in Computer Science, vol. 10328 (Springer, Berlin), 241–253.Google Scholar
• [33] Huang C, Sellier F (2022) Maximum weight b-matchings in random-order streams. Chechik S, Navarro G, Rotenberg E, Herman G, eds. 30th Annual Eur. Sympos. Algorithms ESA 2022, LIPIcs, vol. 244 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 68:1–68:14.Google Scholar
• [34] Huang C, Sellier F (2024) Robust sparsification for matroid intersection with applications. Woodruff DP, ed. Proc. 2024 ACM-SIAM Sympos. Discrete Algorithms SODA 2024 (SIAM, Philadelphia), 2916–2940.Google Scholar
• [35] Kapralov M (2013) Better bounds for matchings in the streaming model. Khanna S, ed. Proc. Twenty-Fourth Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2013 (SIAM, Philadelphia), 1679–1697.Google Scholar
• [36] Kapralov M (2021) Space lower bounds for approximating maximum matching in the edge arrival model. Marx D, ed. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms SODA 2021 (SIAM, Philadelphia), 1874–1893.Google Scholar
• [37] Kiss P (2022) Deterministic dynamic matching in worst-case update time. Braverman M, ed. 13th Innovations Theoret. Comput. Sci. Conf. ITCS 2022, LIPIcs, vol. 215 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 94:1–94:21.Google Scholar
• [38] Konrad C (2018) A simple augmentation method for matchings with applications to streaming algorithms. Potapov I, Spirakis PG, Worrell J, eds. 43rd Internat. Sympos. Math. Foundations Comput. Sci. MFCS 2018, LIPIcs, vol. 117 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 74:1–74:16.Google Scholar
• [39] Konrad C, Magniez F, Mathieu C (2012) Maximum matching in semi-streaming with few passes. Gupta A, Jansen K, Rolim JDP, Servedio RA, eds. Approximation Randomization Combin. Optim. Algorithms Techniques 15th Internat. Workshop APPROX 2012 16th Internat. Workshop RANDOM 2012 Proc., Lecture Notes in Computer Science, vol. 7408 (Springer, Berlin), 231–242.Google Scholar
• [40] Kushilevitz E (1997) Communication complexity. Zelkowitz MV, ed. Advances in Computers, vol. 44 (Elsevier, Amsterdam), 331–360.Google Scholar
• [41] Lee YT, Sidford A, Wong SC (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. Guruswami V, ed. IEEE 56th Annual Sympos. Foundations Comput. Sci. FOCS 2015 (IEEE Computer Society, Washington, DC), 1049–1065.Google Scholar
• [42] Mestre J (2006) Greedy in approximation algorithms. Azar Y, Erlebach T, eds. Algorithms—ESA 2006 14th Annual Eur. Sympos. Proc., Lecture Notes in Computer Science, vol. 4168 (Springer, Berlin), 528–539.Google Scholar
• [43] Murota K (1999) Matrices and Matroids for Systems Analysis, vol. 20 (Springer, Berlin).Google Scholar
• [44] Recski A (1989) Matroid Theory and Its Applications in Electric Network Theory and in Statics (Springer, Berlin).Crossref, Google Scholar
• [45] Roghani M, Saberi A, Wajc D (2022) Beating the folklore algorithm for dynamic matching. Braverman M, ed. 13th Innovations Theoret. Comput. Sci. Conf. ITCS 2022, LIPIcs, vol. 215 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 111:1–111:23.Google Scholar
• [46] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• [47] Xu Y, Gabow HN (1994) Fast algorithms for transversal matroid intersection problems. Du D, Zhang X, eds. Algorithms Comput. 5th Internat. Sympos. ISAAC ‘94 Proc., Lecture Notes in Computer Science, vol. 834 (Springer, Berlin), 625–633.Google Scholar