{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:54Z","timestamp":1740109374672,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T00:00:00Z","timestamp":1610323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T00:00:00Z","timestamp":1610323200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["160364472 \u2014 SFB 901\/3"],"award-info":[{"award-number":["160364472 \u2014 SFB 901\/3"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["160364472 \u2014 SFB 901\/3"],"award-info":[{"award-number":["160364472 \u2014 SFB 901\/3"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["160364472 \u2014 SFB 901\/3"],"award-info":[{"award-number":["160364472 \u2014 SFB 901\/3"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We extend the Mobile Server problem introduced in Feldkord and Meyer auf der Heide (TOPC <jats:bold>6<\/jats:bold>(3), 14:1\u201314:17 2019) to a model where <jats:italic>k<\/jats:italic> identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. To reduce communication costs, the positions of the servers can be adapted by a limited distance <jats:italic>m<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub> per round for each server. The costs are measured similarly to the classical Page Migration problem: i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight <jats:italic>D<\/jats:italic>. We show that, in our model, no online algorithm can have a constant competitive ratio: i.e., one which is independent of the input length <jats:italic>n<\/jats:italic>, even if an augmented moving distance of (1 + <jats:italic>\u03b4<\/jats:italic>)<jats:italic>m<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub> is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand <jats:italic>locality of requests<\/jats:italic>: i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant <jats:italic>m<\/jats:italic><jats:sub><jats:italic>c<\/jats:italic><\/jats:sub>. We show constant lower bounds on the competitiveness in this setting (independent of <jats:italic>n<\/jats:italic>, but dependent on <jats:italic>k<\/jats:italic>, <jats:italic>m<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub> and <jats:italic>m<\/jats:italic><jats:sub><jats:italic>c<\/jats:italic><\/jats:sub>). On the positive side, we present a deterministic online algorithm with bounded competitiveness when an augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical <jats:italic>k<\/jats:italic>-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers <jats:italic>k<\/jats:italic>, the ratio between <jats:italic>m<\/jats:italic><jats:sub><jats:italic>c<\/jats:italic><\/jats:sub> and <jats:italic>m<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub>, the inverse of the augmentation factor 1\/<jats:italic>\u03b4<\/jats:italic> and the competitive ratio of the simulated <jats:italic>k<\/jats:italic>-Page Migration algorithm. We also show how to directly adapt the Double Coverage algorithm (Chrobak et al. SIAM J. Discrete Math. <jats:bold>4<\/jats:bold>(2), 172\u2013181 11) for the <jats:italic>k<\/jats:italic>-Server problem to receive an algorithm with improved competitiveness on the line.<\/jats:p>","DOI":"10.1007\/s00224-020-10023-8","type":"journal-article","created":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T12:39:07Z","timestamp":1610368747000},"page":"943-984","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Managing Multiple Mobile Resources"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6591-2420","authenticated-orcid":false,"given":"Bj\u00f6rn","family":"Feldkord","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Knollmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Malatyali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm Meyer auf der","family":"Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,11]]},"reference":[{"issue":"5","key":"10023_CR1","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1016\/j.jcss.2015.11.005","volume":"82","author":"S Albers","year":"2016","unstructured":"Albers, S., Lauer, S.: On list update with locality of reference. J. Comput. Syst. Sci. 82(5), 627\u2013653 (2016). https:\/\/doi.org\/10.1016\/j.jcss.2015.11.005","journal-title":"J. Comput. Syst. Sci."},{"key":"10023_CR2","doi-asserted-by":"publisher","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: List update with locality of reference. In: Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN). https:\/\/doi.org\/10.1007\/978-3-540-78773-0_35, pp 399\u2013410. Springer (2008)","DOI":"10.1007\/978-3-540-78773-0_35"},{"issue":"5","key":"10023_CR3","doi-asserted-by":"publisher","first-page":"40:1","DOI":"10.1145\/2783434","volume":"62","author":"N Bansal","year":"2015","unstructured":"Bansal, N., Buchbinder, N., Madry, A., Naor, J.: A polylogarithmic-competitive algorithm for the k-server problem. J. ACM 62(5), 40:1\u201340:49 (2015). https:\/\/doi.org\/10.1145\/2783434","journal-title":"J. ACM"},{"issue":"1","key":"10023_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0304-3975(00)00259-0","volume":"268","author":"Y Bartal","year":"2001","unstructured":"Bartal, Y., Charikar, M., Indyk, P.: On page migration and other relaxed task systems. Theor. Comput. Sci. 268(1), 43\u201366 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00259-0","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"10023_CR5","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2004.06.001","volume":"324","author":"Y Bartal","year":"2004","unstructured":"Bartal, Y., Koutsoupias, E.: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2\u20133), 337\u2013345 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.06.001","journal-title":"Theor. Comput. Sci."},{"key":"10023_CR6","doi-asserted-by":"publisher","unstructured":"Bienkowski, M., Byrka, J., Coester, C., Jez, L.: Unbounded lower bound for k-server against weak adversaries. In: Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp 1165\u20131169. ACM (2020), https:\/\/doi.org\/10.1145\/3357713.3384306","DOI":"10.1145\/3357713.3384306"},{"issue":"4","key":"10023_CR7","doi-asserted-by":"publisher","first-page":"46,1","DOI":"10.1145\/3340296","volume":"15","author":"M Bienkowski","year":"2019","unstructured":"Bienkowski, M., Byrka, J., Mucha, M.: Dynamic beats fixed: On phase-based algorithms for file migration. ACM Trans. Algorithms 15(4), 46,1\u201346,21 (2019). https:\/\/doi.org\/10.1145\/3340296","journal-title":"ACM Trans. Algorithms"},{"key":"10023_CR8","unstructured":"Black, D.L., Sleator, D.D.: Competitive algorithms for replication and migration problems. Tech. Rep. CMU-CS-89-201, Department of Computer Science Carnegie-Mellon University (1989)"},{"issue":"2","key":"10023_CR9","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. J. Comput. Syst. Sci. 50(2), 244\u2013258 (1995). https:\/\/doi.org\/10.1006\/jcss.1995.1021","journal-title":"J. Comput. Syst. Sci."},{"key":"10023_CR10","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Cohen, M.B., Lee, Y.T., Lee, J.R., Madry, A.: k-server via multiscale entropic regularization. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/doi.org\/10.1145\/3188745.3188798, pp 3\u201316 (2018)","DOI":"10.1145\/3188745.3188798"},{"issue":"2","key":"10023_CR11","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4(2), 172\u2013181 (1991). https:\/\/doi.org\/10.1137\/0404017","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"10023_CR12","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3364204","volume":"6","author":"B Feldkord","year":"2019","unstructured":"Feldkord, B., Meyer auf der Heide, F.: The mobile server problem. TOPC 6(3), 14:1\u201314:17 (2019). https:\/\/doi.org\/10.1145\/3364204","journal-title":"TOPC"},{"issue":"4","key":"10023_CR13","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A Fiat","year":"1991","unstructured":"Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12(4), 685\u2013699 (1991). https:\/\/doi.org\/10.1016\/0196-6774(91)90041-V","journal-title":"J. Algorithms"},{"key":"10023_CR14","doi-asserted-by":"publisher","unstructured":"Fiat, A., Mendel, M.: Truly online paging with locality of reference. In: 38th Annual Symposium on Foundations of Computer Science (FOCS). https:\/\/doi.org\/10.1109\/SFCS.1997.646121, pp 326\u2013335. IEEE Computer Society (1997)","DOI":"10.1109\/SFCS.1997.646121"},{"key":"10023_CR15","doi-asserted-by":"publisher","unstructured":"Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 444\u2013449. https:\/\/doi.org\/10.1109\/SFFCS.1999.814616 (1999)","DOI":"10.1109\/SFFCS.1999.814616"},{"issue":"5","key":"10023_CR16","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971\u2013983 (1995). https:\/\/doi.org\/10.1145\/210118.210128","journal-title":"J. ACM"},{"key":"10023_CR17","doi-asserted-by":"publisher","unstructured":"Lee, J.R.: Fusible hsts and the randomized k-server conjecture. In: Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 438\u2013449. https:\/\/doi.org\/10.1109\/FOCS.2018.00049 (2018)","DOI":"10.1109\/FOCS.2018.00049"},{"issue":"2","key":"10023_CR18","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208\u2013230 (1990). https:\/\/doi.org\/10.1016\/0196-6774(90)90003-W","journal-title":"J. Algorithms"},{"issue":"1","key":"10023_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s10100-011-0222-7","volume":"21","author":"T Rudec","year":"2013","unstructured":"Rudec, T., Baumgartner, A., Manger, R.: A fast work function algorithm for solving the k-server problem. CEJOR 21(1), 187\u2013205 (2013). https:\/\/doi.org\/10.1007\/s10100-011-0222-7","journal-title":"CEJOR"},{"issue":"3","key":"10023_CR20","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/s10100-014-0349-4","volume":"23","author":"T Rudec","year":"2015","unstructured":"Rudec, T., Manger, R.: A fast approximate implementation of the work function algorithm for solving the k-server problem. CEJOR 23(3), 699\u2013722 (2015). https:\/\/doi.org\/10.1007\/s10100-014-0349-4","journal-title":"CEJOR"},{"issue":"5","key":"10023_CR21","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1137\/S0097539791199796","volume":"23","author":"JR Westbrook","year":"1994","unstructured":"Westbrook, J.R.: Randomized algorithms for multiprocessor page migration. SIAM J. Comput. 23(5), 951\u2013965 (1994). https:\/\/doi.org\/10.1137\/S0097539791199796","journal-title":"SIAM J. Comput."},{"key":"10023_CR22","doi-asserted-by":"publisher","unstructured":"Zhang, W., Cheng, Y.: A new upper bound on the work function algorithm for the k-server problem. Journal of Combinatorial Optimization. https:\/\/doi.org\/10.1007\/s10878-019-00493-z (2019)","DOI":"10.1007\/s10878-019-00493-z"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10023-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10023-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10023-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,7]],"date-time":"2021-08-07T22:03:44Z","timestamp":1628373824000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10023-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,11]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10023"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10023-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2021,1,11]]},"assertion":[{"value":"7 December 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}