{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:58:56Z","timestamp":1773327536793,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NWO Vici","award":["639.023.812"],"award-info":[{"award-number":["639.023.812"]}]},{"name":"NWO Vidi","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}]},{"name":"ERC consolidator","award":["617951"],"award-info":[{"award-number":["617951"]}]},{"DOI":"10.13039\/501100002661","name":"FNRS","doi-asserted-by":"crossref","award":["MISU F 6001 1"],"award-info":[{"award-number":["MISU F 6001 1"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NWO Veni","award":["639.021.438"],"award-info":[{"award-number":["639.021.438"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            The generalized\n            <jats:italic>k<\/jats:italic>\n            -server problem is a far-reaching extension of the\n            <jats:italic>k<\/jats:italic>\n            -server problem with several applications. Here, each server\n            <jats:italic>\n              s\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            lies in its own metric space\n            <jats:italic>\n              M\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            . A request is a\n            <jats:italic>k<\/jats:italic>\n            -tuple\n            <jats:italic>r<\/jats:italic>\n            = (\n            <jats:italic>r<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>r<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ,\u2026 ,\n            <jats:italic>\n              r\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            , which is served by moving some server\n            <jats:italic>\n              s\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            to the point\n            <jats:italic>\n              r\n              <jats:sub>i<\/jats:sub>\n              \u2208 M\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            , and the goal is to minimize the total distance traveled by the servers. Despite much work, no\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )-competitive algorithm is known for the problem for\n            <jats:italic>k<\/jats:italic>\n            &gt; 2 servers, even for special cases such as uniform metrics and lines.\n          <\/jats:p>\n          <jats:p>\n            Here, we consider the problem in uniform metrics and give the first\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )-competitive algorithms for general\n            <jats:italic>k<\/jats:italic>\n            . In particular, we obtain deterministic and randomized algorithms with competitive ratio\n            <jats:italic>k<\/jats:italic>\n            \u00b7 2\n            <jats:italic>\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            log\n            <jats:italic>k<\/jats:italic>\n            ), respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2\n            <jats:italic>\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            -1. We also give a 2\n            <jats:sup>\n              2\n              <jats:sup>\n                <jats:italic>O(k)<\/jats:italic>\n              <\/jats:sup>\n            <\/jats:sup>\n            -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.\n          <\/jats:p>","DOI":"10.1145\/3568677","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T12:22:21Z","timestamp":1670934141000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Competitive Algorithms for Generalized\n            <i>k<\/i>\n            -Server in Uniform Metrics"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6290-0894","authenticated-orcid":false,"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4583-8897","authenticated-orcid":false,"given":"Marek","family":"Eli\u00e1\u0161","sequence":"additional","affiliation":[{"name":"Bocconi University, Milan, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4928-103X","authenticated-orcid":false,"given":"Grigorios","family":"Koumoutsos","sequence":"additional","affiliation":[{"name":"Lightcurve GmbH, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Utrecht University, CC Utrecht, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2023,2,20]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_3_3_3_2","first-page":"254","volume-title":"Proceeding of the ISAAC","author":"Augustine John","year":"2010","unstructured":"John Augustine and Nick Gravin. 2010. On the continuous CNN problem. In Proceeding of the ISAAC. 254\u2013265."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.9"},{"issue":"5","key":"e_1_3_3_5_2","first-page":"40","article-title":"A polylogarithmic-competitive algorithm for the k-server Problem","volume":"62","author":"Bansal Nikhil","year":"2015","unstructured":"Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. 2015. A polylogarithmic-competitive algorithm for the k-server Problem. Journal of the ACM 62, 5 (2015), 40.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.52"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.64"},{"key":"e_1_3_3_8_2","first-page":"14:1\u201314:14","volume-title":"Proceedings of the Symposium on Algorithms and Computation, ISAAC 2019","author":"Bienkowski Marcin","year":"2019","unstructured":"Marcin Bienkowski, \u0141ukasz Je\u017c, and Pawe\u0142 Schmidt. 2019. Slaying hydrae: Improved bounds for generalized k-server in uniform metrics. In Proceedings of the Symposium on Algorithms and Computation, ISAAC 2019. 14:1\u201314:14."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188798"},{"key":"e_1_3_3_12_2","unstructured":"Ashish Chiplunkar. Oct 2016. (Oct 2016). Personal Communication."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365002"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/954092.954104"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404017"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00607-3"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","unstructured":"J. S. Ellenberg and D. Gijswijt. 2017. On large subsets of  \\(F_q^n\\)  with no three-term arithmetic progression. Ann. Math. 185 1 (2017) 339\u2013343.","DOI":"10.4007\/annals.2017.185.1.8"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90154-6"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","DOI":"10.1090\/ulect\/064","volume-title":"Polynomial Methods in Combinatorics","author":"Guth L.","year":"2016","unstructured":"L. Guth. 2016. Polynomial Methods in Combinatorics. American Mathematical Society."},{"key":"e_1_3_3_22_2","first-page":"1","article-title":"Axis-bound CNN problem","author":"Iwama Kazuo","year":"2001","unstructured":"Kazuo Iwama and Kouki Yonezawa. 2001. Axis-bound CNN problem. IEICE TRANS (2001), 1\u20138.","journal-title":"IEICE TRANS"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.022"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.006"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17364-6","volume-title":"Extremal Combinatorics - With Applications in Computer Science","author":"Jukna Stasys","year":"2011","unstructured":"Stasys Jukna. 2011. Extremal Combinatorics - With Applications in Computer Science. Springer."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00010-5"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.002"},{"issue":"2","key":"e_1_3_3_29_2","first-page":"208","article-title":"Competitive algorithms for server problems","volume":"11","author":"Manasse Mark S.","year":"1990","unstructured":"Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. 1990. Competitive algorithms for server problems. Journal of the ACM 11, 2 (1990), 208\u2013230.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_30_2","volume-title":"Proceedings of the 33rd Miniatures: Mathematical and Algorithmic Applications of Linear Algebra","author":"Matou\u0161ek Ji\u0159\u00ed","year":"2010","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 2010. In Proceedings of the 33rd Miniatures: Mathematical and Algorithmic Applications of Linear Algebra. American Mathematical Society."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/120885309"},{"key":"e_1_3_3_33_2","first-page":"624","volume-title":"ICALP","author":"Sitters Ren\u00e9","year":"2003","unstructured":"Ren\u00e9 Sitters, Leen Stougie, and Willem de Paepe. 2003. A competitive algorithm for the general 2-server problem. In ICALP. 624\u2013636."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147960"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568677","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:34Z","timestamp":1750183714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3568677"],"URL":"https:\/\/doi.org\/10.1145\/3568677","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2020-05-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}