{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:30Z","timestamp":1759638090112,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T00:00:00Z","timestamp":1549411200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2016\/22\/E\/ST6\/00499"],"award-info":[{"award-number":["2016\/22\/E\/ST6\/00499"]}],"id":[{"id":"10.13039\/501100004281","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":[[2019,4,30]]},"abstract":"<jats:p>\n            We study the\n            <jats:italic>k<\/jats:italic>\n            -server problem in the resource augmentation setting, i.e.,\u00a0when the performance of the online algorithm with\n            <jats:italic>k<\/jats:italic>\n            servers is compared to the offline optimal solution with\n            <jats:italic>h<\/jats:italic>\n            \u2264\n            <jats:italic>k<\/jats:italic>\n            servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic\n            <jats:italic>k<\/jats:italic>\n            -server algorithms are roughly (1+1\/\u03f5)-competitive when\n            <jats:italic>k<\/jats:italic>\n            =(1+\u03f5)\n            <jats:italic>h<\/jats:italic>\n            , for any \u03f5 &gt; 0. Surprisingly, however, no\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>h<\/jats:italic>\n            )-competitive algorithm is known even for HSTs of depth 2 and even when\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>h<\/jats:italic>\n            is arbitrarily large.\n          <\/jats:p>\n          <jats:p>\n            We obtain several new results for the problem. First, we show that the known\n            <jats:italic>k<\/jats:italic>\n            -server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio \u03a9 (\n            <jats:italic>h<\/jats:italic>\n            ) irrespective of the value of\n            <jats:italic>k<\/jats:italic>\n            , even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>h<\/jats:italic>\n            , has competitive ratio \u03a9 (\n            <jats:italic>h<\/jats:italic>\n            ) on depth-3 HSTs even if\n            <jats:italic>k<\/jats:italic>\n            =2\n            <jats:italic>h<\/jats:italic>\n            . Our main result is a new algorithm that is\n            <jats:italic>O<\/jats:italic>\n            (1)-competitive for constant depth trees, whenever\n            <jats:italic>k<\/jats:italic>\n            =(1+\u03f5)\n            <jats:italic>h<\/jats:italic>\n            for any \u03f5 &gt; 0. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2.4 even for depth-2 HSTs and when\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>h<\/jats:italic>\n            is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the (\n            <jats:italic>h<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-server problem.\n          <\/jats:p>","DOI":"10.1145\/3301314","type":"journal-article","created":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T19:16:27Z","timestamp":1549480587000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The (\n            <i>h,k<\/i>\n            )-Server Problem on Bounded Depth Trees"],"prefix":"10.1145","volume":"15","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"CWI and TU Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Eli\u00e9\u0161","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0141ukasz","family":"Je\u017c","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigorios","family":"Koumoutsos","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Bansal Nikhil","year":"2017","unstructured":"Nikhil Bansal , Marek Eli\u00e1s , Lukasz Jez , and Grigorios Koumoutsos . 2017 . The (h, k)-server problem on bounded depth trees . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . 1022--1037. Nikhil Bansal, Marek Eli\u00e1s, Lukasz Jez, and Grigorios Koumoutsos. 2017. The (h, k)-server problem on bounded depth trees. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 1022--1037."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9703-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.001"},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_5_1","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_2_1_8_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--14: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--14:14."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796506"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_14_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\/3301314","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:04Z","timestamp":1750208524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,6]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3301314"],"URL":"https:\/\/doi.org\/10.1145\/3301314","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,2,6]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}