{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T03:18:43Z","timestamp":1768274323082,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["IIS-2147361"],"award-info":[{"award-number":["IIS-2147361"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2210501"],"award-info":[{"award-number":["CCF-2210501"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["2046146"],"award-info":[{"award-number":["2046146"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,9]]},"DOI":"10.1145\/3580507.3597794","type":"proceedings-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T14:19:22Z","timestamp":1688739562000},"page":"185-205","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The Power of Greedy for Online Minimum Cost Matching on the Line"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6876-7919","authenticated-orcid":false,"given":"Eric","family":"Balkanski","sequence":"first","affiliation":[{"name":"Columbia University, New York, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3148-2159","authenticated-orcid":false,"given":"Yuri","family":"Faenza","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7854-4057","authenticated-orcid":false,"given":"No\u00e9mie","family":"P\u00e9rivier","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538375"},{"key":"e_1_3_2_1_2_1","volume-title":"Workshop on Approximation and Online Algorithms.","author":"Antoniadis Antonios Foivos","year":"2014","unstructured":"Antonios Foivos Antoniadis , Neal Barcelo , Michael Nugent , Kirk Pruhs , and Michele Scquizzato . 2014 . A o(n) -Competitive Deterministic Algorithm for Online Matching on a Line . In Workshop on Approximation and Online Algorithms. Antonios Foivos Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. 2014. A o(n) -Competitive Deterministic Algorithm for Online Matching on a Line. In Workshop on Approximation and Online Algorithms."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2021.0082"},{"key":"e_1_3_2_1_4_1","volume-title":"2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 405--414","author":"Arthur David","year":"2009","unstructured":"David Arthur , Bodo Manthey , and Heiko R\u00f6glin . 2009 . K-means has polynomial smoothed complexity . In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 405--414 . David Arthur, Bodo Manthey, and Heiko R\u00f6glin. 2009. K-means has polynomial smoothed complexity. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 405--414."},{"key":"e_1_3_2_1_5_1","volume-title":"The Simultaneous Semi-random Model for TSP. In International Conference on Integer Programming and Combinatorial Optimization. Springer, 43--56","author":"Balkanski Eric","year":"2022","unstructured":"Eric Balkanski , Yuri Faenza , and Mathieu Kubik . 2022 . The Simultaneous Semi-random Model for TSP. In International Conference on Integer Programming and Combinatorial Optimization. Springer, 43--56 . Eric Balkanski, Yuri Faenza, and Mathieu Kubik. 2022. The Simultaneous Semi-random Model for TSP. In International Conference on Integer Programming and Combinatorial Optimization. Springer, 43--56."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778629"},{"key":"e_1_3_2_1_7_1","volume-title":"Matchmaking in Lyft Line - Part 1. Lyft Engineering","author":"Brown Timothy","year":"2016","unstructured":"Timothy Brown . 2016. Matchmaking in Lyft Line - Part 1. Lyft Engineering ( 2016 ). https:\/\/tinyurl.com\/3sdrw7yc Timothy Brown. 2016. Matchmaking in Lyft Line - Part 1. Lyft Engineering (2016). https:\/\/tinyurl.com\/3sdrw7yc"},{"key":"e_1_3_2_1_8_1","volume-title":"Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA","author":"Chatziafratis Vaggos","year":"2017","unstructured":"Vaggos Chatziafratis , Tim Roughgarden , and Jan Vondrak . 2017 . Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrak. 2017. Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_9_1","volume-title":"Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete applied mathematics 7, 3","author":"Conforti Michele","year":"1984","unstructured":"Michele Conforti and G\u00e9rard Cornu\u00e9jols . 1984. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete applied mathematics 7, 3 ( 1984 ), 251--274. Michele Conforti and G\u00e9rard Cornu\u00e9jols. 1984. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete applied mathematics 7, 3 (1984), 251--274."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0037-5"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993581"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2972953"},{"key":"e_1_3_2_1_14_1","volume-title":"Introduction to Semirandom Models. Beyond the Worst-Case Analysis of Algorithms","author":"Feige Uriel","year":"2021","unstructured":"Uriel Feige . 2021. Introduction to Semirandom Models. Beyond the Worst-Case Analysis of Algorithms ( 2021 ), 189. Uriel Feige. 2021. Introduction to Semirandom Models. Beyond the Worst-Case Analysis of Algorithms (2021), 189."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_16"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219045"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00436-6"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2019.01.002"},{"key":"e_1_3_2_1_19_1","first-page":"982","article-title":"Online budgeted matching in random input models with applications to Adwords","volume":"8","author":"Goel Gagan","year":"2008","unstructured":"Gagan Goel and Aranyak Mehta . 2008 . Online budgeted matching in random input models with applications to Adwords .. In SODA , Vol. 8. 982 -- 991 . Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords.. In SODA, Vol. 8. 982--991.","journal-title":"SODA"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.67"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"e_1_3_2_1_22_1","unstructured":"Varun Gupta Ravishankar Krishnaswamy and Sai Sandeep. 2020. PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching. In APPROX-RANDOM.  Varun Gupta Ravishankar Krishnaswamy and Sai Sandeep. 2020. PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching. In APPROX-RANDOM."},{"key":"e_1_3_2_1_23_1","volume-title":"Uber drivers are reportedly colluding to trigger 'surge' prices because they say the company is not paying them enough. Insider","author":"Hamilton Isobel Asher","year":"2019","unstructured":"Isobel Asher Hamilton . 2019. Uber drivers are reportedly colluding to trigger 'surge' prices because they say the company is not paying them enough. Insider ( 2019 ). https:\/\/www.businessinsider.com\/uber-drivers-artificially-triggering-surge-prices-reports-abc7-2019-6 Isobel Asher Hamilton. 2019. Uber drivers are reportedly colluding to trigger 'surge' prices because they say the company is not paying them enough. Insider (2019). https:\/\/www.businessinsider.com\/uber-drivers-artificially-triggering-surge-prices-reports-abc7-2019-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1452"},{"key":"e_1_3_2_1_25_1","volume-title":"How Uber Eats Uses Machine Learning to Estimate Delivery Times? The New Stack","author":"Jackson Joab","year":"2019","unstructured":"Joab Jackson . 2019. How Uber Eats Uses Machine Learning to Estimate Delivery Times? The New Stack ( 2019 ). https:\/\/thenewstack.io\/how-uber-eats-uses-machine-learning-to-estimate-delivery-times\/ Joab Jackson. 2019. How Uber Eats Uses Machine Learning to Estimate Delivery Times? The New Stack (2019). https:\/\/thenewstack.io\/how-uber-eats-uses-machine-learning-to-estimate-delivery-times\/"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198342310"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2105.07329"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538278"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_3_2_1_31_1","volume-title":"The Online Matching Problem on a Line","author":"Koutsoupias Elias","unstructured":"Elias Koutsoupias and Akash Nanavati . 2004. The Online Matching Problem on a Line . In Approximation and Online Algorithms, Roberto Solis-Oba and Klaus Jansen (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 179--191. Elias Koutsoupias and Akash Nanavati. 2004. The Online Matching Problem on a Line. In Approximation and Online Algorithms, Roberto Solis-Oba and Klaus Jansen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 179--191."},{"key":"e_1_3_2_1_32_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"K\u00fcnnemann Marvin","unstructured":"Marvin K\u00fcnnemann and Bodo Manthey . 2015. Towards understanding the smoothed approximation ratio of the 2-opt heuristic . In International Colloquium on Automata, Languages, and Programming . Springer , 859--871. Marvin K\u00fcnnemann and Bodo Manthey. 2015. Towards understanding the smoothed approximation ratio of the 2-opt heuristic. In International Colloquium on Automata, Languages, and Programming. Springer, 859--871."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00359-w"},{"key":"e_1_3_2_1_34_1","first-page":"94","article-title":"Worst-case and smoothed analysis of k-means clustering with Bregman divergences","volume":"4","author":"Manthey Bodo","year":"2013","unstructured":"Bodo Manthey and Heiko R\u00f6glin . 2013 . Worst-case and smoothed analysis of k-means clustering with Bregman divergences . Journal of Computational Geometry (Old Web Site) 4 , 1 (2013), 94 -- 132 . Bodo Manthey and Heiko R\u00f6glin. 2013. Worst-case and smoothed analysis of k-means clustering with Bregman divergences. Journal of Computational Geometry (Old Web Site) 4, 1 (2013), 94--132.","journal-title":"Journal of Computational Geometry (Old Web Site)"},{"key":"e_1_3_2_1_35_1","volume-title":"Greedy online bipartite matching on random graphs. arXiv preprint arXiv:1307.2536","author":"Mastin Andrew","year":"2013","unstructured":"Andrew Mastin and Patrick Jaillet . 2013. Greedy online bipartite matching on random graphs. arXiv preprint arXiv:1307.2536 ( 2013 ). Andrew Mastin and Patrick Jaillet. 2013. Greedy online bipartite matching on random graphs. arXiv preprint arXiv:1307.2536 (2013)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.37"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Aranyak Mehta et al. 2013. Online matching and ad allocation. Foundations and Trends\u00ae in Theoretical Computer Science 8 4 (2013) 265--368.  Aranyak Mehta et al. 2013. Online matching and ad allocation. Foundations and Trends\u00ae in Theoretical Computer Science 8 4 (2013) 265--368.","DOI":"10.1561\/0400000057"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109662"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.53"},{"key":"e_1_3_2_1_41_1","volume-title":"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 [EQUATION]-competitive algorithm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Enoch Peserico and Michele Scquizzato. 2021. Matching on the line admits no [EQUATION]-competitive algorithm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_42_1","volume-title":"International Conference on Machine Learning. PMLR, 7772--7782","author":"Pokutta Sebastian","year":"2020","unstructured":"Sebastian Pokutta , Mohit Singh , and Alfredo Torrico . 2020 . On the unreasonable effectiveness of the greedy algorithm: Greedy adapts to sharpness . In International Conference on Machine Learning. PMLR, 7772--7782 . Sebastian Pokutta, Mohit Singh, and Alfredo Torrico. 2020. On the unreasonable effectiveness of the greedy algorithm: Greedy adapts to sharpness. In International Conference on Machine Learning. PMLR, 7772--7782."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.18"},{"key":"e_1_3_2_1_44_1","volume-title":"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 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Sharath Raghvendra. 2018. Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line. In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_45_1","volume-title":"Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS","author":"Rubinstein Aviad","year":"2022","unstructured":"Aviad Rubinstein and Junyao Zhao . 2022 . Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Aviad Rubinstein and Junyao Zhao. 2022. Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994523"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00116-2"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"33","author":"Xu Pan","year":"2019","unstructured":"Pan Xu , Yexuan Shi , Hao Cheng , John Dickerson , Karthik Abinav Sankararaman , Aravind Srinivasan , Yongxin Tong , and Leonidas Tsepenekas . 2019 . A unified approach to online matching with conflict-aware constraints . In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 33 . 2221--2228. Pan Xu, Yexuan Shi, Hao Cheng, John Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Yongxin Tong, and Leonidas Tsepenekas. 2019. A unified approach to online matching with conflict-aware constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 2221--2228."}],"event":{"name":"EC '23: 24th ACM Conference on Economics and Computation","location":"London United Kingdom","acronym":"EC '23","sponsor":["SIGecom Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 24th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597794","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580507.3597794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:34Z","timestamp":1750178794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":48,"alternative-id":["10.1145\/3580507.3597794","10.1145\/3580507"],"URL":"https:\/\/doi.org\/10.1145\/3580507.3597794","relation":{},"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"2023-07-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}