{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T11:40:02Z","timestamp":1747136402518,"version":"3.40.5"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007837","name":"Universit\u00e4t Bremen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In online metric matching on the line, <jats:italic>n<\/jats:italic> requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all located on the real line. The goal is to minimize the sum of distances between the requests and their assigned servers. The best known online algorithm achieves a competitive ratio of\u00a0<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, leaving a gap to the best-known lower bound of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Omega (\\sqrt{\\log n})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mrow>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. In this work, we approach the problem in a recourse model where online decisions can be partially revised, allowing for the reassignment of previously matched edges. In contrast to the traditional online setting, we show that with an amortized recourse budget of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, we can obtain an <jats:italic>O<\/jats:italic>(1)-competitive algorithm for online metric matching on the line. This is one of the first non-trivial results for metric matching with recourse. Additionally, for so-called alternating instances, where no more than one request lies between two servers, we achieve a near-optimal result. Specifically, we give a simple algorithm that is\u00a0<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$(1+\\varepsilon )$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-competitive and reassigns any request at most\u00a0<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\frac{1}{\\varepsilon ^2})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:msup>\n                        <mml:mi>\u03b5<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                    <\/mml:mfrac>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> times. This special case is particularly noteworthy, as a lower bound of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Omega (\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature.<\/jats:p>","DOI":"10.1007\/s00453-025-01299-8","type":"journal-article","created":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:40:21Z","timestamp":1740811221000},"page":"813-841","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Metric Matching on the Line with Recourse"],"prefix":"10.1007","volume":"87","author":[{"given":"Nicole","family":"Megow","sequence":"first","affiliation":[]},{"given":"Lukas","family":"N\u00f6lke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,1]]},"reference":[{"key":"1299_CR1","unstructured":"Angelopoulos, S., D\u00fcrr, C., Jin, S.: Online maximum matching with recourse. In: MFCS, volume 117 of LIPIcs, pp. 8:1\u20138:15 (2018)"},{"key":"1299_CR2","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Fischer, C., T\u00f6nnis, A.: A collection of lower bounds for online matching on the line. In: LATIN, volume 10807 of LNCS, pp. 52\u201365 (2018)","DOI":"10.1007\/978-3-319-77404-6_5"},{"issue":"2","key":"1299_CR3","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","volume":"68","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Buchbinder, N., Gupta, A., Naor, J.: A randomized $$O(\\log ^2 k)$$-competitive algorithm for metric bipartite matching. Algorithmica 68(2), 390\u2013403 (2014)","journal-title":"Algorithmica"},{"key":"1299_CR4","unstructured":"Bernstein, A., Dudeja, A.: Online matching with recourse: random edge arrivals. In: FSTTCS, volume 182 of LIPIcs, pp. 11:1\u201311:16 (2020)"},{"issue":"5","key":"1299_CR5","doi-asserted-by":"publisher","first-page":"37:1","DOI":"10.1145\/3344999","volume":"66","author":"A Bernstein","year":"2019","unstructured":"Bernstein, A., Holm, J., Rotenberg, E.: Online bipartite matching with amortized $$O(\\log ^2 n)$$ replacements. J. ACM 66(5), 37:1-37:23 (2019)","journal-title":"J. ACM"},{"key":"1299_CR6","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In: FOCS, pp. 384\u2013393 (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"1299_CR7","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R., Lin, H.: Online bipartite perfect matching with augmentations. In: INFOCOM, pp. 1044\u20131052 (2009)","DOI":"10.1109\/INFCOM.2009.5062016"},{"issue":"1","key":"1299_CR8","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2529989","volume":"61","author":"R Duan","year":"2014","unstructured":"Duan, R., Pettie, S.: Linear-time approximation for maximum weight matching. J. ACM 61(1), 1:1-1:23 (2014)","journal-title":"J. ACM"},{"issue":"2","key":"1299_CR9","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.orl.2019.01.002","volume":"47","author":"M Gairing","year":"2019","unstructured":"Gairing, M., Klimm, M.: Greedy metric minimum online matchings with random arrivals. Oper. Res. Lett. 47(2), 88\u201391 (2019)","journal-title":"Oper. Res. Lett."},{"key":"1299_CR10","doi-asserted-by":"crossref","unstructured":"Grove, E., Kao, M., Krishnan, P., Vitter, J.: Online perfect matching and mobile computing. In: WADS, volume 955 of LNCS, pp. 194\u2013205 (1995)","DOI":"10.1007\/3-540-60220-8_62"},{"issue":"1","key":"1299_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/140955276","volume":"45","author":"A Gu","year":"2016","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant-competitive Steiner tree online. SIAM J. Comput. 45(1), 1\u201328 (2016)","journal-title":"SIAM J. Comput."},{"key":"1299_CR12","unstructured":"Gupta, A., Guruganesh, G., Peng, B., Wajc, D.: Stochastic online metric matching. In: ICALP, volume 132 of LIPIcs, pp. 67:1\u201367:14 (2019)"},{"key":"1299_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: matching, scheduling, and flows. In: SODA, pp. 468\u2013479 (2014)","DOI":"10.1137\/1.9781611973402.35"},{"key":"1299_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lewi, K.: The online metric matching problem for doubling metrics. In: ICALP, volume 7391 of LNCS, pp. 424\u2013435 (2012)","DOI":"10.1007\/978-3-642-31594-7_36"},{"key":"1299_CR15","unstructured":"Gupta, V., Krishnaswamy, R., Sandeep, S.: Permutation strikes back: the power of recourse in online metric matching. In: APPROX-RANDOM, volume 176 of LIPIcs, pp. 40:1\u201340:20 (2020)"},{"issue":"3","key":"1299_CR16","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.: Dynamic Steiner tree problem. SIAM J. Discrete Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"1299_CR17","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"key":"1299_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R., Vazirani, U., Vazirani, V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"issue":"2","key":"1299_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S., Vazirani, V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"1299_CR20","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W., Yaw, B.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2, 83\u201397 (1955)","journal-title":"Naval Res. Logist. Quart."},{"key":"1299_CR21","doi-asserted-by":"crossref","unstructured":"Lacki, J., O\u0107wieja, J., Pilipczuk, M., Sankowski, P., Zych, A.: The power of dynamic distance oracles: efficient dynamic algorithms for the Steiner tree. In: STOC, pp. 11\u201320 (2015)","DOI":"10.1145\/2746539.2746615"},{"key":"1299_CR22","unstructured":"Matuschke, J., Schmidt-Kraepelin, U., Verschae, J.: Maintaining perfect matchings at low cost. In: ICALP, volume 132 of LIPIcs, pp. 82:1\u201382:14 (2019)"},{"key":"1299_CR23","unstructured":"Megow, N., N\u00f6lke, L.: Online minimum cost matching with recourse on the line. In: APPROX-RANDOM, volume 176 of LIPIcs, pp. 37:1\u201337:16 (2020)"},{"issue":"3","key":"1299_CR24","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/130917703","volume":"45","author":"N Megow","year":"2016","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. SIAM J. Comput. 45(3), 859\u2013880 (2016)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1299_CR25","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"1299_CR26","doi-asserted-by":"crossref","unstructured":"Nayyar, K., Raghvendra, S.: An input sensitive online algorithm for the metric bipartite matching problem. In: FOCS, pp. 505\u2013515 (2017)","DOI":"10.1109\/FOCS.2017.53"},{"key":"1299_CR27","doi-asserted-by":"crossref","unstructured":"Peserico, E., Scquizzato, M.: Matching on the line admits no $$o(\\sqrt{\\log n})$$-competitive algorithm. In: ICALP, volume 198 of LIPIcs, pp. 103:1\u2013103:3 (2021)","DOI":"10.1145\/3594873"},{"key":"1299_CR28","unstructured":"Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: APPROX-RANDOM, volume\u00a060 of LIPIcs, pp. 18:1\u201318:16 (2016)"},{"key":"1299_CR29","unstructured":"Raghvendra, S.: Optimal analysis of an online algorithm for the bipartite matching problem on a line. In: SoCG, volume\u00a099 of LIPIcs, pp. 67:1\u201367:14 (2018)"},{"key":"1299_CR30","unstructured":"Shin, Y., Kim, K., Lee, S., An, H.: Online graph matching problems with a worst-case reassignment budget (2020). CoRR arXiv:2003.05175"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01299-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01299-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01299-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T11:23:28Z","timestamp":1747135408000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01299-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,1]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1299"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01299-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,3,1]]},"assertion":[{"value":"22 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}