LIPIcs.ICALP.2021.103.pdf
- Filesize: 0.52 MB
- 3 pages
Document
Matching on the Line Admits No o(√log n)-Competitive Algorithm
Authors
-
Part of:
Volume:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-02
File
Document Identifiers
Acknowledgements
We are indebted to Kirk Pruhs and the anonymous reviewers for their constructive criticism and insightful observations.
Cite As Get BibTex
Enoch Peserico and Michele Scquizzato. Matching on the Line Admits No o(√log n)-Competitive Algorithm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 103:1-103:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.103
Abstract
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line exceeds √{log₂(n +1)}/15 for all n = 2ⁱ-1: i ∈ ℕ, settling a 25-year-old open question.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
Keywords
- Metric matching
- online algorithms
- competitive analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. A o(n)-competitive deterministic algorithm for online matching on a line. Algorithmica, 81(7):2917-2933, 2019.
-
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of the 37th ICML, pages 345-355, 2020.
-
Antonios Antoniadis, Carsten Fischer, and Andreas Tönnis. A collection of lower bounds for online matching on the line. In Proceedings of the 13th LATIN, pages 52-65, 2018.
-
Bernhard Fuchs, Winfried Hochstättler, and Walter Kern. Online matching on a line. Theor. Comput. Sci., 332(1-3):251-264, 2005.
-
Anupam Gupta and Kevin Lewi. The online metric matching problem for doubling metrics. In Proceedings of the 39th ICALP, pages 424-435, 2012.
-
Varun Gupta, Ravishankar Krishnaswamy, and Sai Sandeep. Permutation strikes back: The power of recourse in online metric matching. In Proceedings of the 23rd APPROX, pages 40:1-40:20, 2020.
-
Bala Kalyanasundaram and Kirk Pruhs. Online weighted matching. J. Algorithms, 14(3):478-488, 1993.
-
Bala Kalyanasundaram and Kirk Pruhs. Online network optimization problems. In Online Algorithms: The State of the Art, pages 268-280. Springer-Verlag, 1998. From the Dagstuhl Seminar on Online Algorithms, 1996.
-
Samir Khuller, Stephen G. Mitchell, and Vijay V. Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci., 127(2):255-267, 1994.
-
Elias Koutsoupias and Akash Nanavati. The online matching problem on a line. In Proceedings of the 1st WAOA, pages 179-191, 2003.
-
Nicole Megow and Lukas Nölke. Online minimum cost matching with recourse on the line. In Proceedings of the 23rd APPROX, pages 37:1-37:16, 2020.
-
Krati Nayyar and Sharath Raghvendra. An input sensitive online algorithm for the metric bipartite matching problem. In Proceedings of the 58th IEEE FOCS, pages 505-515, 2017.
-
Sharath Raghvendra. Optimal analysis of an online algorithm for the bipartite matching problem on a line. In Proceedings of the 34th SoCG, pages 67:1-67:14, 2018.
-
Rob van Stee. SIGACT news online algorithms column 27: Online matching on the line, part 1. SIGACT News, 47(1):99-110, 2016.