Online Metric Matching: Beyond the Worst Case

References

• Akbarpour M, Li S, Gharan SO (2020) Thickness and information in dynamic matching markets. J. Political Econom. 128(3):783–815.Crossref, Google Scholar
• Akbarpour M, Alimohammadi Y, Li S, Saberi A (2022) The value of excess supply in spatial matching markets. Pennock DM, Segal I, Seuken S, eds. EC ‘22 Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 62.Google Scholar
• Almanza M, Chierichetti F, Lattanzi S, Panconesi A, Re G (2021) Online facility location with multiple advice. Ranzato MA, Beygelzimer A, Dauphin YN, Liang P, Vaughan JW, eds. Annual Conf. Neural Inform. Processing Systems (NeurIPS) (Curran Associates Inc., Red Hook, NY), 4661–4673.Google Scholar
• Anand K, Ge R, Kumar A, Panigrahi D (2022) Online algorithms with multiple predictions. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., vol. 162 (PMLR, New York), 582–598.Google Scholar
• Anderson R, Ashlagi I, Gamarnik D, Kanoria Y (2017) Efficient dynamic barter exchange. Oper. Res. 65(6):1446–1459.Link, Google Scholar
• Antoniadis A, Gouleakis T, Kleer P, Kolev P (2023a) Secretary and online matching problems with machine learned advice. Discrete Optim. 48(Part 2):100778.Crossref, Google Scholar
• Antoniadis A, Barcelo N, Nugent M, Pruhs K, Scquizzato M (2019) A o(n)-competitive deterministic algorithm for online matching on a line. Algorithmica 81(7):2917–2933.Crossref, Google Scholar
• Antoniadis A, Coester C, Eliás M, Polak A, Simon B (2023b) Mixing predictions for online metric algorithms. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. ICML Proc. Machine Learn. Res., vol. 202 (PMLR, New York), 969–983.Google Scholar
• Antoniadis A, Coester C, Eliás M, Polak A, Simon B (2023c) Online metric algorithms with untrusted predictions. ACM Trans. Algorithms 19(2):19.Crossref, Google Scholar
• Balkanski E, Faenza Y, Périvier N (2023) The power of greedy for online minimum cost matching on the line. Brown KL, Hartline JD, Samuelson L, eds. ACM Conf. Econom. Comput. (ACM, New York), 185–205.Google Scholar
• Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res. 72(5):2168–2189.Link, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Bansal N, Buchbinder N, Gupta A, Naor J (2014) A randomized O(log2 k)-competitive algorithm for metric bipartite matching. Algorithmica 68(2):390–403.Crossref, Google Scholar
• Berger B, Feldman M, Gkatzelis V, Tan X (2024) Learning-augmented metric distortion via (p, q)-veto core. Bergemann D, Kleinberg R, Sabán D, eds. ACM Conf. Econom. Comput. (ACM, New York), 984.Google Scholar
• Besbes O, Kanoria Y, Kumar A (2023) Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances. Preprint, submitted October 6, https://arxiv.org/abs/2205.09078.Google Scholar
• Bobkov S, Ledoux M (2019) One-Dimensional Empirical Measures, Order Statistics, and Kantorovich Transport Distances, vol. 261 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Bray RL (2025) Logarithmic regret in multisecretary and online linear programs with continuous valuations. Oper. Res. 73(4):2188–2203.Link, Google Scholar
• Chen Y, Kanoria Y, Kumar A, Zhang W (2023) Feature based dynamic matching. Brown KL, Hartline JD, Samuelson L, eds. ACM Conf. Econom. Comput. (ACM, New York), 451.Google Scholar
• Dobrić V, Yukich JE (1995) Asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8(1):97–118.Crossref, Google Scholar
• Fuchs B, Hochstättler W, Kern W (2005) Online matching on a line. Theoret. Comput. Sci. 332(1–3):251–264.Crossref, Google Scholar
• Gairing M, Klimm M (2019) Greedy metric minimum online matchings with random arrivals. Oper. Res. Lett. 47(2):88–91.Crossref, Google Scholar
• Gupta V (2024) Greedy algorithm for multiway matching with bounded regret. Oper. Res. 72(3):1139–1155.Link, Google Scholar
• Gupta A, Lewi K (2012) The online metric matching problem for doubling metrics. Czumaj A, Mehlhorn K, Pitts AM, Wattenhofer R, eds. Internat. Colloquium Automata Languages Programming (ICALP) (Springer, Berlin, Heidelberg), 424–435.Google Scholar
• Gupta A, Guruganesh G, Peng B, Wajc D (2019) Stochastic online metric matching. Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, eds. Internat. Colloquium Automata Languages Programming (ICALP) (Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Wadern, Germany), 67.Google Scholar
• Gupta A, Panigrahi D, Subercaseaux B, Sun K (2022) Augmenting online algorithms with ε-accurate predictions. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Annual Conf. Neural Inform. Processing Systems (NeurIPS) (Association for Computing Machinery, New York).Google Scholar
• Huang Z, Tang ZG, Wajc D (2024) Online matching: A brief survey. Preprint, submitted July 7, https://arxiv.org/abs/2407.05381.Google Scholar
• Jiang J, Ma W, Zhang J (2022a) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Naor JS, Buchbinder N, eds. Proc. 33th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1221–1246.Google Scholar
• Jiang J, Ma W, Zhang J (2025) Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions. Preprint, submitted January 2, https://arxiv.org/abs/2210.07996.Google Scholar
• Jiang SH, Liu E, Lyu Y, Tang ZG, Zhang Y (2022b) Online facility location with predictions. 10th Internat. Conf. Learn. Representations (ICLR) (OpenReview.net).Google Scholar
• Jin B, Ma W (2022) Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Annual Conf. Neural Inform. Processing Systems (NeurIPS) (Curran Associates Inc., Red Hook, NY).Google Scholar
• Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J. Algorithms 14(3):478–488.Crossref, Google Scholar
• Kanoria Y (2022) Dynamic spatial matching. Pennock DM, Segal I, Seuken S, eds. ACM Conf. Econom. Comput. (ACM, New York), 63–64.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Ortiz H, ed. STOC ‘90 Proc. Twenty-Second Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
• Kerimov S, Qian P, Yang M, Yu SH (2025) Achieving constant regret for dynamic matching via state-independent policies. Preprint, submitted March 12, https://arxiv.org/abs/2503.09762.Google Scholar
• Khuller S, Mitchell SG, Vazirani VV (1994) On-line algorithms for weighted bipartite matching and stable marriages. Theoret. Comput. Sci. 127(2):255–267.Crossref, Google Scholar
• Lykouris T, Vassilvitskii S (2021) Competitive caching with machine learned advice. J. ACM 68(4):24.Crossref, Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Meyerson A, Nanavati A, Poplawski LJ (2006) Randomized online algorithms for minimum metric bipartite matching. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (ACM Press, New York), 954–959.Google Scholar
• Nayyar K, Raghvendra S (2017) An input sensitive online algorithm for the metric bipartite matching problem. Umans C, ed. Proc. 58st Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 505–515.Google Scholar
• Peserico E, Scquizzato M (2023) Matching on the line admits no o(√log n)-competitive algorithm. ACM Trans. Algorithms 19(3):28.Crossref, Google Scholar
• Raghvendra S (2016) A robust and optimal online algorithm for minimum metric bipartite matching. Jansen K, Mathieu C, Rolim JDP, Umans C, eds. Internat. Conf. Randomization Comput. (RANDOM) Internat. Conf. Approximation Algorithms Combin. Optim. Problems (APPROX) (Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Wadern, Germany), 18.Google Scholar
• Raghvendra S (2018) Optimal analysis of an online algorithm for the bipartite matching problem on a line. Speckmann B, Tóth CD, eds. Sympos. Comput. Geometry (SoCG) (Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Wadern, Germany), 67.Google Scholar
• Talagrand M (1992) The Ajtai–Komlós–Tusnády matching theorem for general measures. Dudley RM, Hahn MG, Kuelbs J, eds. Probab. Banach Spaces 8 Proc. Eighth Internat. Conf. (Springer, Boston), 39–54.Google Scholar
• Talagrand M (2022) Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems, vol. 60 (Springer Nature, Cham, Switzerland).Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• Wei Y, Xu J, Yu SH (2023) Constant regret primal-dual policy for multi-way dynamic matching. ACM SIGMETRICS Performance Evaluation Rev. 51(1):79–80.Crossref, Google Scholar