{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:23:40Z","timestamp":1773325420273,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,9,30]],"date-time":"2019-09-30T00:00:00Z","timestamp":1569801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation (DFG) within the Collaborative Research Centre \u201dOn-The-Fly Computing\u201e","award":["160364472-SFB 901\/2"],"award-info":[{"award-number":["160364472-SFB 901\/2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>We introduce the Mobile Server problem, inspired by current trends to move computational tasks from cloud structures to multiple devices close to the end user. An example of this is embedded systems in autonomous cars that communicate to coordinate their actions.<\/jats:p>\n          <jats:p>\n            Our model is a variant of the classical Page Migration problem. More formally, we consider a mobile server holding a data page. The server can move in the Euclidean space (of arbitrary dimension). In every round, requests for data items from the page pop up at arbitrary points in the space. The requests are served, each at a cost of the distance from the requesting point and the server, and the mobile server may move, at a cost\n            <jats:italic>D<\/jats:italic>\n            times the distance traveled for some constant\n            <jats:italic>D<\/jats:italic>\n            . We assume a maximum distance\n            <jats:italic>m<\/jats:italic>\n            that the server is allowed to move per round.\n          <\/jats:p>\n          <jats:p>We show that no online algorithm can achieve a competitive ratio independent of the length of the input sequence in this setting. Hence, we augment the maximum movement distance of the online algorithms to (1+&amp;delta) times the maximum distance of the offline solution. We provide a deterministic algorithm that is simple to describe and works for multiple variants of our problem. The algorithm achieves almost tight competitive ratios independent of the length of the input sequence.<\/jats:p>\n          <jats:p>Our algorithm also achieves a constant competitive ratio without resource augmentation in a variant where the movement of clients is also restricted.<\/jats:p>","DOI":"10.1145\/3364204","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T16:35:58Z","timestamp":1571157358000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Mobile Server Problem"],"prefix":"10.1145","volume":"6","author":[{"given":"Bj\u00f6rn","family":"Feldkord","sequence":"first","affiliation":[{"name":"Heinz Nixdorf Institut 8 Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm Meyer Auf","family":"Der Heide","sequence":"additional","affiliation":[{"name":"Heinz Nixdorf Institut 8 Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCO.2016.7727082"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672860"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00055-5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00259-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00305-X"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.07.006"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917)","author":"Bienkowski Marcin","year":"2017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.01.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0853"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 13th International World Wide Web Conference on Alternate Track Papers and Posters. ACM","author":"Davis A."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch104"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492478"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3390\/a9030057"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087578"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9841-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791199796"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 18th IEEE Annual Symposium Foundations of Computer Science (FOCS\u201977)","author":"Chi-Chin Yao Andrew","year":"1977"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:26Z","timestamp":1750203866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,30]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3364204"],"URL":"https:\/\/doi.org\/10.1145\/3364204","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,30]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}