{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T15:00:56Z","timestamp":1773327656868,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T00:00:00Z","timestamp":1652400000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T00:00:00Z","timestamp":1652400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"US-Israel BSF","award":["2018352"],"award-info":[{"award-number":["2018352"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2233\/19 (2027511)"],"award-info":[{"award-number":["2233\/19 (2027511)"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NWO","award":["VICI 639.023.812"],"award-info":[{"award-number":["VICI 639.023.812"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"Abstract<\/jats:title>We consider the online k<\/jats:italic>-taxi problem, a generalization of the k<\/jats:italic>-server problem, in which k<\/jats:italic> servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger<\/jats:italic>. We show that the classic Double Coverage<\/jats:italic> algorithm has competitive ratio $$2^k-1$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on HSTs, matching a recent lower bound for deterministic algorithms. For bounded depth HSTs, the competitive ratio turns out to be much better and we obtain tight bounds. When the depth is $$d\\ll k$$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u226a<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, these bounds are approximately $$k^d\/d!$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n \/<\/mml:mo>\n d<\/mml:mi>\n !<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. By standard embedding results, we obtain a randomized algorithm for arbitrary n<\/jats:italic>-point metrics with (polynomial) competitive ratio $$O(k^c\\Delta ^{1\/c}\\log _{\\Delta } n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msup>\n \n \u0394<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \n log<\/mml:mo>\n \u0394<\/mml:mi>\n <\/mml:msub>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\Delta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the aspect ratio and $$c\\ge 1$$<\/jats:tex-math>\n \n c<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is an arbitrary positive integer constant. The previous known bound was $$O(2^k\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For general (weighted) tree metrics, we prove the competitive ratio of Double Coverage to be $$\\Theta (k^d)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any fixed depth d<\/jats:italic>, and in contrast to HSTs it is not bounded by $$2^k-1$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We obtain our results by a dual fitting analysis where the dual solution is constructed step-by-step backwards<\/jats:italic> in time. Unlike the forward-time approach typical of online primal-dual analyses, this allows us to combine information from both the past and the future when assigning dual variables. We believe this method can also be useful for other problems. Using this technique, we also provide a dual fitting proof of the k<\/jats:italic>-competitiveness of Double Coverage for the k<\/jats:italic>-server problem on trees.\n<\/jats:p>","DOI":"10.1007\/s10107-022-01815-6","type":"journal-article","created":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T11:08:00Z","timestamp":1652440080000},"page":"499-527","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online k-taxi via Double Coverage and time-reverse primal-dual"],"prefix":"10.1007","volume":"197","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3744-0977","authenticated-orcid":false,"given":"Christian","family":"Coester","sequence":"additional","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,13]]},"reference":[{"key":"1815_CR1","doi-asserted-by":"crossref","unstructured":"Azar, Y., Buchbinder, N., Hubert Chan, T.-H., Chen, S., Cohen, I.R., Gupta, A., Huang, Z., Kang, N., Nagarajan, V., Naor, J., Panigrahi, D.: Online algorithms for covering and packing problems with convex objectives. In IEEE 57th annual symposium on foundations of computer science, FOCS 2016, pp. 148\u2013157. IEEE Computer Society, (2016)","DOI":"10.1109\/FOCS.2016.24"},{"key":"1815_CR2","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In In 37th annual symposium on foundations of computer science, FOCS \u201996, pp. 184\u2013193, (1996)"},{"issue":"1","key":"1815_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R.M., Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica 11(1), 2\u201314 (1994)","journal-title":"Algorithmica"},{"key":"1815_CR4","unstructured":"Bubeck, S., Buchbinder, N., Coester, C., Sellke, M.: Metrical service systems with transformations. In 12th innovations in theoretical computer science conference, ITCS 2021, vol. 185, pp. 21:1\u201321:20, (2021)"},{"key":"1815_CR5","doi-asserted-by":"crossref","unstructured":"Bubeck, S., Cohen, M.B., Lee, Yin T., Lee, J.R., Madry, A.: k-server via multiscale entropic regularization. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC 2018, pp. 3\u201316. ACM, (2018)","DOI":"10.1145\/3188745.3188798"},{"key":"1815_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Gupta, A., Molinaro, M., Naor, J(Seffi).: k-servers with a smile: online algorithms via projections. In Proceedings of the Thirtieth annual ACM-SIAM symposium on discrete algorithms, SODA 2019, pp. 98\u2013116. SIAM, (2019)","DOI":"10.1137\/1.9781611975482.7"},{"issue":"2\u20133","key":"1815_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2\u20133), 93\u2013263 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"1815_CR8","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H., Payne, T., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4(2), 172\u2013181 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1815_CR9","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Larmore, L.L.: An optimal on-line algorithm for k servers on trees. SIAM J. Comput. 20(1), 144\u2013148 (1991)","journal-title":"SIAM J. Comput."},{"key":"1815_CR10","doi-asserted-by":"crossref","unstructured":"Coester, C., Koutsoupias, E.: The online $$k$$-taxi problem. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC 2019, pp. 1136\u20131147. ACM, (2019)","DOI":"10.1145\/3313276.3316370"},{"key":"1815_CR11","unstructured":"Dehghani, S., Ehsani, S., Hajiaghayi, M., Liaghat, V., Seddighin, S.: Stochastic k-Server: How Should Uber Work? In 44th international colloquium on automata, languages, and programming (ICALP 2017), pp. 126:1\u2013126:14, (2017)"},{"key":"1815_CR12","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1815_CR13","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A Fiat","year":"1991","unstructured":"Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12(4), 685\u2013699 (1991)","journal-title":"J. Algorithms"},{"key":"1815_CR14","unstructured":"Fiat, A., Rabani, Y., Ravid, Y.: Competitive k-server algorithms (extended abstract). In 31st Annual symposium on foundations of computer science, FOCS \u201990, pp. 454\u2013463, (1990)"},{"issue":"4","key":"1815_CR15","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1287\/moor.2014.0652","volume":"39","author":"A Gupta","year":"2014","unstructured":"Gupta, A., Nagarajan, V.: Approximating sparse covering integer programs online. Math. Oper. Res. 39(4), 998\u20131011 (2014)","journal-title":"Math. Oper. Res."},{"key":"1815_CR16","unstructured":"Kosoresow, A.P.: Design and analysis of online algorithms for mobile server applications. PhD thesis, Stanford University, (1996)"},{"issue":"2","key":"1815_CR17","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105\u2013118 (2009)","journal-title":"Comput. Sci. Rev."},{"issue":"5","key":"1815_CR18","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971\u2013983 (1995)","journal-title":"J. ACM"},{"key":"1815_CR19","doi-asserted-by":"crossref","unstructured":"Lee, J.R.: Fusible HSTs and the randomized k-server conjecture. In Proceedings of the 59th Annual IEEE symposium on foundations of computer science, FOCS \u201918, pp. 438\u2013449, (2018)","DOI":"10.1109\/FOCS.2018.00049"},{"key":"1815_CR20","doi-asserted-by":"crossref","unstructured":"Lee, J.R.: Fusible HSTs and the randomized k-server conjecture. arXiv:1711.01789, February (2018)","DOI":"10.1109\/FOCS.2018.00049"},{"key":"1815_CR21","unstructured":"Lee, J.R.: Personal Communication (2019)"},{"key":"1815_CR22","doi-asserted-by":"crossref","unstructured":"Manasse, M., McGeoch, L., Sleator, D.: Competitive algorithms for on-line problems. In Proceedings of the twentieth annual ACM symposium on theory of computing, STOC \u201988, pp. 322\u2013333. ACM, (1988)","DOI":"10.1145\/62212.62243"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01815-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01815-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01815-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:20:31Z","timestamp":1675704031000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01815-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,13]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1815"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01815-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,13]]},"assertion":[{"value":"28 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}