{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:15:23Z","timestamp":1761621323879,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1535972, 1527084"],"award-info":[{"award-number":["1535972, 1527084"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055475","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"551-563","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Online service with delay"],"prefix":"10.1145","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arun","family":"Ganesh","sequence":"additional","affiliation":[{"name":"Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Ge","sequence":"additional","affiliation":[{"name":"Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Anna Adamaszek Artur Czumaj Matthias Englert and Harald R\u00e4cke. 2011.  Anna Adamaszek Artur Czumaj Matthias Englert and Harald R\u00e4cke. 2011."},{"key":"e_1_3_2_1_2_1","unstructured":"Almost tight bounds for reordering buffer management. In STOC. 607\u2013616.  Almost tight bounds for reordering buffer management. In STOC. 607\u2013616."},{"key":"e_1_3_2_1_3_1","volume-title":"Joseph SB Mitchell, and Giri Narasimhan","author":"Arkin Esther M","year":"1998","unstructured":"Esther M Arkin , Joseph SB Mitchell, and Giri Narasimhan . 1998 . Esther M Arkin, Joseph SB Mitchell, and Giri Narasimhan. 1998."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276919"},{"key":"e_1_3_2_1_5_1","volume-title":"4th International Workshop, WADS \u201995","author":"Ausiello Giorgio","year":"1995","unstructured":"Giorgio Ausiello , Esteban Feuerstein , Stefano Leonardi , Leen Stougie , and Maurizio Talamo . 1995 . Competitive Algorithms for the On-line Traveling Salesman. In Algorithms and Data Structures , 4th International Workshop, WADS \u201995 , Kingston, Ontario, Canada , August 16-18, 1995, Proceedings. 206\u2013217. Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, and Maurizio Talamo. 1995. Competitive Algorithms for the On-line Traveling Salesman. In Algorithms and Data Structures, 4th International Workshop, WADS \u201995, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. 206\u2013217."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010071"},{"key":"e_1_3_2_1_7_1","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 78\u201390","author":"Avigdor-Elgrabli Noa","year":"2015","unstructured":"Noa Avigdor-Elgrabli , Sungjin Im , Benjamin Moseley , and Yuval Rabani . 2015 . On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 78\u201390 . Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, and Yuval Rabani. 2015. On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 78\u201390."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Noa Avigdor-Elgrabli and Yuval Rabani. 2010. An Improved Competitive Algorithm for Reordering Buffer Management. In SODA. 13\u201321.   Noa Avigdor-Elgrabli and Yuval Rabani. 2010. An Improved Competitive Algorithm for Reordering Buffer Management. In SODA. 13\u201321.","DOI":"10.1137\/1.9781611973075.2"},{"key":"e_1_3_2_1_9_1","volume-title":"An Optimal Randomized Online Algorithm for Reordering Buffer Management. CoRR abs\/1303.3386","author":"Avigdor-Elgrabli Noa","year":"2013","unstructured":"Noa Avigdor-Elgrabli and Yuval Rabani . 2013. An Optimal Randomized Online Algorithm for Reordering Buffer Management. CoRR abs\/1303.3386 ( 2013 ). Noa Avigdor-Elgrabli and Yuval Rabani. 2013. An Optimal Randomized Online Algorithm for Reordering Buffer Management. CoRR abs\/1303.3386 (2013)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528826X"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039753"},{"key":"e_1_3_2_1_12_1","unstructured":"Yossi Azar and Adi Vardi. 2015.  Yossi Azar and Adi Vardi. 2015."},{"key":"e_1_3_2_1_13_1","volume-title":"CoRR abs\/1501.06158","author":"Time Windows TSP","year":"2015","unstructured":"TSP with Time Windows and Service Time . CoRR abs\/1501.06158 ( 2015 ). TSP with Time Windows and Service Time. CoRR abs\/1501.06158 (2015)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007385"},{"key":"e_1_3_2_1_15_1","unstructured":"Nikhil Bansal Niv Buchbinder Aleksander Madry and Joseph Naor. 2015.  Nikhil Bansal Niv Buchbinder Aleksander Madry and Joseph Naor. 2015."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783434"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.11.002"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_15"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946322"},{"key":"e_1_3_2_1_20_1","unstructured":"Allan Borodin and Ran El-Yaniv. 1998.  Allan Borodin and Ran El-Yaniv. 1998."},{"volume-title":"Cambridge University Press","author":"Computation Online","key":"e_1_3_2_1_21_1","unstructured":"Online Computation and Competitive Analysis . Cambridge University Press , New York, NY, USA . Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_2_1_22_1","volume-title":"Approximation algorithms for orienteering with time windows. arXiv preprint arXiv:0711.4825","author":"Chekuri Chandra","year":"2007","unstructured":"Chandra Chekuri and Nitish Korula . 2007. Approximation algorithms for orienteering with time windows. arXiv preprint arXiv:0711.4825 ( 2007 ). Chandra Chekuri and Nitish Korula. 2007. Approximation algorithms for orienteering with time windows. arXiv preprint arXiv:0711.4825 (2007)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229167"},{"key":"e_1_3_2_1_24_1","unstructured":"Chandra Chekuri and Amit Kumar. 2004.  Chandra Chekuri and Amit Kumar. 2004."},{"volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Maximum","key":"e_1_3_2_1_25_1","unstructured":"Maximum coverage problem with group budget constraints and applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 72\u201383. Maximum coverage problem with group budget constraints and applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 72\u201383."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897557"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a002"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_51"},{"key":"e_1_3_2_1_29_1","unstructured":"Jittat Fakcharoenphol Satish Rao and Kunal Talwar. 2004.  Jittat Fakcharoenphol Satish Rao and Kunal Talwar. 2004."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644030"},{"key":"e_1_3_2_1_32_1","volume-title":"The orienteering problem. Naval research logistics 34, 3","author":"Golden Bruce L","year":"1987","unstructured":"Bruce L Golden , Larry Levy , and Rakesh Vohra . 1987. The orienteering problem. Naval research logistics 34, 3 ( 1987 ), 307\u2013318. Bruce L Golden, Larry Levy, and Rakesh Vohra. 1987. The orienteering problem. Naval research logistics 34, 3 (1987), 307\u2013318."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000019683.85186.57"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00596-6"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_48"},{"volume-title":"Approximation and Online Algorithms","author":"Krumke Sven O","key":"e_1_3_2_1_36_1","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_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Harald R\u00e4cke Christian Sohler and Matthias Westermann. 2002. Online Scheduling for Sorting Buffers.. In ESA. 820\u2013832.  Harald R\u00e4cke Christian Sohler and Matthias Westermann. 2002. Online Scheduling for Sorting Buffers.. In ESA. 820\u2013832.","DOI":"10.1007\/3-540-45749-6_71"},{"key":"e_1_3_2_1_38_1","unstructured":"John N Tsitsiklis. 1992.  John N Tsitsiklis. 1992."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Montreal Canada","acronym":"STOC '17"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055475","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055475","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":38,"alternative-id":["10.1145\/3055399.3055475","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055475","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}