{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T21:30:31Z","timestamp":1781559031244,"version":"3.54.5"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian National Center for HPC, Big Data, and Quantum Computing, and by Univ. Padova","award":["BIRD197859\/19"],"award-info":[{"award-number":["BIRD197859\/19"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>\n            We present a simple proof that no randomized online matching algorithm for the line can be\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((\\sqrt {\\log _2(n+1)}\/15)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -competitive against an oblivious adversary for any\n            <jats:italic>n<\/jats:italic>\n            = 2\n            <jats:sup>\n              <jats:italic\/>\n              i\n            <\/jats:sup>\n            - 1 :\n            <jats:italic>i<\/jats:italic>\n            \u2208 \u2115. This is the first super-constant lower bound for the problem, and disproves as a corollary a recent conjecture on the topology-parametrized competitiveness achievable on generic spaces.\n          <\/jats:p>","DOI":"10.1145\/3594873","type":"journal-article","created":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T12:18:13Z","timestamp":1684930693000},"page":"1-4","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Matching on the Line Admits no  \\(o(\\sqrt {\\log n})\\) -Competitive Algorithm"],"prefix":"10.1145","volume":"19","author":[{"given":"Enoch","family":"Peserico","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9108-2448","authenticated-orcid":false,"given":"Michele","family":"Scquizzato","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00565-w"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582689"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_5"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.028"},{"key":"e_1_3_1_6_2","first-page":"67:1\u201367:14","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Gupta Anupam","year":"2019","unstructured":"Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. 2019. Stochastic online metric matching. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 67:1\u201367:14."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"e_1_3_1_8_2","first-page":"40:1\u201340:20","volume-title":"Proceedings of the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Gupta Varun","year":"2020","unstructured":"Varun Gupta, Ravishankar Krishnaswamy, and Sai Sandeep. 2020. Permutation strikes back: The power of recourse in online metric matching. In Proceedings of the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 40:1\u201340:20."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/BFb0029573","volume-title":"Online Algorithms: The State of the Art","author":"Kalyanasundaram Bala","year":"1998","unstructured":"Bala Kalyanasundaram and Kirk Pruhs. 1998. Online network optimization oroblems. In Online Algorithms: The State of the Art. Springer-Verlag, 268\u2013280. From the Dagstuhl Seminar on Online Algorithms, 1996."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198342310"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90042-6"},{"key":"e_1_3_1_13_2","first-page":"179","volume-title":"Proceedings of the 1st International Workshop on Approximation and Online Algorithms (WAOA)","author":"Koutsoupias Elias","year":"2003","unstructured":"Elias Koutsoupias and Akash Nanavati. 2003. The online matching problem on a line. In Proceedings of the 1st International Workshop on Approximation and Online Algorithms (WAOA). 179\u2013191."},{"key":"e_1_3_1_14_2","first-page":"37:1\u201337:16","volume-title":"Proceedings of the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Megow Nicole","year":"2020","unstructured":"Nicole Megow and Lukas N\u00f6lke. 2020. Online minimum cost matching with recourse on the line. In Proceedings of the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 37:1\u201337:16."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.53"},{"key":"e_1_3_1_16_2","first-page":"103:1\u2013103:3","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Peserico Enoch","year":"2021","unstructured":"Enoch Peserico and Michele Scquizzato. 2021. Matching on the line admits no \\(o(\\sqrt {\\log n})\\) -competitive algorithm. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP). 103:1\u2013103:3."},{"key":"e_1_3_1_17_2","first-page":"67:1\u201367:14","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG)","author":"Raghvendra Sharath","year":"2018","unstructured":"Sharath Raghvendra. 2018. Optimal analysis of an online algorithm for the bipartite matching problem on a line. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG). 67:1\u201367:14."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902945.2902960"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3594873","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3594873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:08Z","timestamp":1750182548000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3594873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3594873"],"URL":"https:\/\/doi.org\/10.1145\/3594873","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,14]]},"assertion":[{"value":"2022-01-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}