{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:26Z","timestamp":1750220426505,"version":"3.41.0"},"reference-count":28,"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"}],"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            We study a variant of the\n            <jats:italic>k<\/jats:italic>\n            -server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the resource augmentation version of the\n            <jats:italic>k<\/jats:italic>\n            -server problem, also known as the\n            <jats:italic>(h,k)<\/jats:italic>\n            -server problem, in which an online algorithm with\n            <jats:italic>k<\/jats:italic>\n            servers competes against an offline algorithm with\n            <jats:italic>h<\/jats:italic>\n            servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the\n            <jats:italic>(h,k)<\/jats:italic>\n            -server problem has bounded competitive ratio for some\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>h<\/jats:italic>\n            ). We give a lower bound of 3.146 for the competitive ratio of the infinite server problem, which holds even for the line and some simple weighted stars. It implies the same lower bound for the\n            <jats:italic>(h,k)<\/jats:italic>\n            -server problem on the line, even when\n            <jats:italic>k\/h<\/jats:italic>\n            \u2192 \u221e, improving on the previous known bounds of 2 for the line and 2.4 for general metrics. For weighted trees and layered graphs, we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case.\n          <\/jats:p>","DOI":"10.1145\/3456632","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Infinite Server Problem"],"prefix":"10.1145","volume":"17","author":[{"given":"Christian","family":"Coester","sequence":"first","affiliation":[{"name":"CWI, Amsterdam, The Netherlands"}]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}]},{"given":"Philip","family":"Lazos","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.63"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783434"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9703-3"},{"key":"e_1_2_1_4_1","first-page":"28","article-title":"The (h, k)-server problem on bounded depth trees","volume":"15","author":"Bansal Nikhil","year":"2019","unstructured":"Nikhil Bansal , Marek Eli\u00e9\u0161 , \u0141ukasz Je\u017c , and Grigorios Koumoutsos . 2019 . The (h, k)-server problem on bounded depth trees . ACM Trans. Alg. 15 , 2 (2019), 28 . Nikhil Bansal, Marek Eli\u00e9\u0161, \u0141ukasz Je\u017c, and Grigorios Koumoutsos. 2019. The (h, k)-server problem on bounded depth trees. ACM Trans. Alg. 15, 2 (2019), 28.","journal-title":"ACM Trans. Alg."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331606"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384306"},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_8_1","unstructured":"Allan Borodin and Ran El-Yaniv . 2005. Online Computation and Competitive Analysis . Cambridge University Press . Allan Borodin and Ran El-Yaniv. 2005. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188798"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_2_1_13_1","volume-title":"Larmore","author":"Chrobak Marek","year":"1992","unstructured":"Marek Chrobak and Lawrence L . Larmore . 1992 . The server problem and on-line games. In On-line Algorithms (DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Vol.7). Citeseer. Marek Chrobak and Lawrence L. Larmore. 1992. The server problem and on-line games. In On-line Algorithms (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol.7). Citeseer."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Coester Christian","year":"2017","unstructured":"Christian Coester , Elias Koutsoupias , and Philip Lazos . 2017 . The infinite server problem . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) . 14:1\u201314:14. Christian Coester, Elias Koutsoupias, and Philip Lazos. 2017. The infinite server problem. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). 14:1\u201314:14."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Cohen Ilan R.","year":"2014","unstructured":"Ilan R. Cohen , Alon Eden , Amos Fiat , and \u0141ukasz Je\u017c . 2014 . Pricing online decisions: Beyond auctions . In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) . SIAM, 73\u201391. Ilan R. Cohen, Alon Eden, Amos Fiat, and \u0141ukasz Je\u017c. 2014. Pricing online decisions: Beyond auctions. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). SIAM, 73\u201391."},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201901)","author":"Csirik J\u00e1nos","key":"e_1_2_1_16_1","unstructured":"J\u00e1nos Csirik , Csan\u00e1d Imreh , John Noga , Steve S. Seiden , and Gerhard J. Woeginger . 2001. Buying a constant competitive ratio for paging . In Proceedings of the European Symposium on Algorithms (ESA\u201901) . Springer, 98\u2013108. J\u00e1nos Csirik, Csan\u00e1d Imreh, John Noga, Steve S. Seiden, and Gerhard J. Woeginger. 2001. Buying a constant competitive ratio for paging. In Proceedings of the European Symposium on Algorithms (ESA\u201901). Springer, 98\u2013108."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Workshop on Approximation and Online Algorithms (WAOA\u201909)","author":"Emek Yuval","year":"2009","unstructured":"Yuval Emek , Pierre Fraigniaud , Amos Korman , and Adi Ros\u00e9n . 2009 . On the additive constant of the k-server work function algorithm . In Proceedings of the International Workshop on Approximation and Online Algorithms (WAOA\u201909) . Springer, 128\u2013134. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Ros\u00e9n. 2009. On the additive constant of the k-server work function algorithm. In Proceedings of the International Workshop on Approximation and Online Algorithms (WAOA\u201909). Springer, 128\u2013134."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 31st Symposium on Foundations of Computer Science (FOCS\u201990)","author":"Fiat Amos","year":"1990","unstructured":"Amos Fiat , Yuval Rabani , and Yiftach Ravid . 1990 . Competitive k-server algorithms (extended abstract) . In Proceedings of the 31st Symposium on Foundations of Computer Science (FOCS\u201990) . 454\u2013463. Amos Fiat, Yuval Rabani, and Yiftach Ravid. 1990. Competitive k-server algorithms (extended abstract). In Proceedings of the 31st Symposium on Foundations of Computer Science (FOCS\u201990). 454\u2013463."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90160-J"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796506"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00010-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00049"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62243"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2nd ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201991)","author":"Young Neal E.","year":"1991","unstructured":"Neal E. Young . 1991 . On-line caching as cache size varies . In Proceedings of the 2nd ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201991) . 241\u2013250. Neal E. Young. 1991. On-line caching as cache size varies. In Proceedings of the 2nd ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201991). 241\u2013250."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456632","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:46:55Z","timestamp":1750193215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3456632"],"URL":"https:\/\/doi.org\/10.1145\/3456632","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2020-01-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"}}]}}