{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T14:22:07Z","timestamp":1778595727406,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1506\/16"],"award-info":[{"award-number":["1506\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF 1535972, CCF 1527084"],"award-info":[{"award-number":["CCF 1535972, CCF 1527084"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>\n            In this article, we introduce the\n            <jats:italic>online service with delay<\/jats:italic>\n            problem. In this problem, there are\n            <jats:italic>n<\/jats:italic>\n            points in a metric space that issue service requests over time, and there is a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, which has many applications in operations management, operating systems, logistics, supply chain management, and scheduling.\n          <\/jats:p>\n          <jats:p>\n            Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the\n            <jats:italic>preemptive service algorithm<\/jats:italic>\n            . The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to\n            <jats:italic>k<\/jats:italic>\n            &gt; 1 servers and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.\n          <\/jats:p>","DOI":"10.1145\/3459925","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Online Service with Delay"],"prefix":"10.1145","volume":"17","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arun","family":"Ganesh","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Ge","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993717"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276919"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672867"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010071"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528826X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.67"},{"key":"e_1_2_1_11_1","unstructured":"Yossi Azar and Adi Vardi. 2015. TSP with time windows and service time. CoRR abs\/1501.06158.  Yossi Azar and Adi Vardi. 2015. TSP with time windows and service time. CoRR abs\/1501.06158."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007385"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783434"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339126"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.11.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_15"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.001"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Bienkowski Marcin","year":"2016","unstructured":"Marcin Bienkowski , Martin B\u00f6hm , Jaroslaw Byrka , Marek Chrobak , Christoph D\u00fcrr , Luk\u00e1\u0161 Folwarczn\u00fd , Lukasz Jez , Jiri Sgall , Nguyen Kim Thang , and Pavel Vesel\u00fd . 2016 . Online algorithms for multi-level aggregation . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . 12:1\u201312:17. Marcin Bienkowski, Martin B\u00f6hm, Jaroslaw Byrka, Marek Chrobak, Christoph D\u00fcrr, Luk\u00e1\u0161 Folwarczn\u00fd, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesel\u00fd. 2016. Online algorithms for multi-level aggregation. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). 12:1\u201312:17."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238180"},{"key":"e_1_2_1_20_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press , New York, NY . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.80"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1188"},{"key":"e_1_2_1_24_1","unstructured":"Chandra Chekuri and Nitish Korula. 2007. Approximation algorithms for orienteering with time windows. arXiv:0711.4825. Retrieved from https:\/\/arxiv.org\/abs\/0711.4825.  Chandra Chekuri and Nitish Korula. 2007. Approximation algorithms for orienteering with time windows. arXiv:0711.4825. Retrieved from https:\/\/arxiv.org\/abs\/0711.4825."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229167"},{"key":"e_1_2_1_26_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Chekuri Chandra","unstructured":"Chandra Chekuri and Amit Kumar . 2004. Maximum coverage problem with group budget constraints and applications . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 72\u201383. Chandra Chekuri and Amit Kumar. 2004. Maximum coverage problem with group budget constraints and applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 72\u201383."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375843"},{"key":"e_1_2_1_30_1","volume-title":"Online matching: Haste makes waste! In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201916). 333\u2013344","author":"Emek Yuval","unstructured":"Yuval Emek , Shay Kutten , and Roger Wattenhofer . 2016. Online matching: Haste makes waste! In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201916). 333\u2013344 . Yuval Emek, Shay Kutten, and Roger Wattenhofer. 2016. Online matching: Haste makes waste! In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201916). 333\u2013344."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a002"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_51"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_2_1_35_1","article-title":"Improved online algorithms for the sorting buffer problem on line metrics","volume":"6","author":"Gamzu Iftah","year":"2009","unstructured":"Iftah Gamzu and Danny Segev . 2009 . Improved online algorithms for the sorting buffer problem on line metrics . ACM Trans. Algor. 6 , 1 (2009), 15:1\u201315:14. Iftah Gamzu and Danny Segev. 2009. Improved online algorithms for the sorting buffer problem on line metrics. ACM Trans. Algor. 6, 1 (2009), 15:1\u201315:14.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0095-6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000019683.85186.57"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1013-x"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00596-6"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_48"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684581"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796506"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_2_1_45_1","volume-title":"Approximation and Online Algorithms","author":"Krumke Sven O.","unstructured":"Sven O. Krumke , Nicole Megow , and Tjark Vredeveld . 2004. How to whack moles . In Approximation and Online Algorithms . Springer , 192\u2013205. Sven O. Krumke, Nicole Megow, and Tjark Vredeveld. 2004. How to whack moles. In Approximation and Online Algorithms. Springer, 192\u2013205."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00049"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_71"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220305"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459925","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459925","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459925","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:51Z","timestamp":1750193331000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459925"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3459925"],"URL":"https:\/\/doi.org\/10.1145\/3459925","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}