On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs

References

• Bennett P, MacRury C (2023) Extending Wormald’s differential equation method to one-sided bounds. Preprint, submitted February 23, https://arxiv.org/abs/2302.12358.Google Scholar
• Brubach B, Grammel N, Ma W, Srinivasan A (2021) Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. Adv. Neural Inform. Processing Systems 34:27184–27195.Google Scholar
• Bruggmann S, Zenklusen R (2022) An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint. Math. Program. 191(2):795–845.Crossref, Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831–1879.Crossref, Google Scholar
• Correa J, Cristi A, Fielbaum A, Pollner T, Weinberg SM (2022) Optimal item pricing in online combinatorial auctions. Aardal K, Sanità L, eds. Internat. Conf. Integer Program. Combinatorial Optim. IPCO 2022 (Springer, Cham, Switzerland), 126–139.Google Scholar
• Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. Twenty-Fourth Annu. ACM-SIAM Sympos. Discrete Algorithms SODA ‘13 (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. Twenty-Ninth Annu. ACM-SIAM Sympos. Discrete Algorithms SODA ‘18 (Society for Industrial and Applied Mathematics, Philadelphia), 700–714.Google Scholar
• Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Link, Google Scholar
• Feldman M, Svensson O, Zenklusen R (2021) Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2):255–300.Crossref, Google Scholar
• Frieze A, Karoński M (2015) Introduction to Random Graphs (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Fu H, Tang ZG, Wu H, Wu J, Zhang Q (2021) Random order vertex arrival contention resolution schemes for matching, with applications. Bansal N, Merelli E, Worrell J, eds. 48th Internat. Colloquium Automata Languages Program. ICALP 2021, Leibniz International Proceedings in Informatics (LIPIcs), vol. 198 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 68:1–68:20.Google Scholar
• Huang Z, Tang Z, Wu X, Zhang Y (2018) Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals. ACM Trans. Algorithms 15(3):1–15.Crossref, Google Scholar
• Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Proc. 2022 Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 1221–1246.Google Scholar
• Karp RM, Sipser M (1981) Maximum matching in sparse random graphs. 22nd Annu. Sympos. Foundations Comput. Sci. SFCS 1981 (IEEE, Piscataway, NJ), 364–375.Google Scholar
• Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Azar Y, Bast H, Herman G, eds. 26th Annu. Eur. Sympos. Algorithms ESA 2018, Leibniz International Proceedings in Informatics LIPIcs, vol. 112 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 57:1–57:14.Google Scholar
• MacRury C, Ma W (2024) Random-order contention resolution via continuous induction: Tightness for bipartite matching under vertex arrivals. Proc. 56th Annu. ACM Sympos. Theory Comput. STOC 2024 (Association for Computing Machinery, New York), 1629–1640.Google Scholar
• MacRury C, Ma W, Grammel N (2023) On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. Proc. 2023 Annual ACM-SIAM Symposium on Discrete Algorithms SODA (Society for Industrial and Applied Mathematics, Philadelphia), 1995–2014.Google Scholar
• Nuti P, Vondrák J (2023) Toward an optimal contention resolution scheme for matchings. Internat. Conf. Integer Program. Combinatorial Optim. (Springer, Cham, Switzerland), 378–392.Google Scholar
• Pollner T, Roghani M, Saberi A, Wajc D (2022) Improved online contention resolution for matchings and applications to the gig economy. Proc. 23rd ACM Conf. Econom. Comput. EC’22 (Association for Computing Machinery, New York), 321–322.Google Scholar
• Raghavan P, Tompson CD (1987) Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4):365–374.Crossref, Google Scholar
• Wormald NC (1999) The differential equation method for random graph processes and greedy algorithms. Lectures on Approximation and Randomized Algorithms (Wydawnictwo Naukowe Pwn, Warszawa, Poland), 73–155.Google Scholar