{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:56Z","timestamp":1740109376639,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T00:00:00Z","timestamp":1696550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100016135","name":"Universit\u00e4t Passau","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016135","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce an online variant of mobile facility location (MFL) (introduced by Demaine et al. (SODA 258\u2013267 2007)). We call this new problem <jats:italic>online mobile facility location<\/jats:italic> (OMFL). In the OMFL problem, initially, we are given a set of <jats:italic>k<\/jats:italic> mobile facilities with their starting locations. One by one, requests are added. After each request arrives, one can make some changes to the facility locations before the subsequent request arrives. Each request is always assigned to the nearest facility. The cost of this assignment is the distance from the request to the facility. The objective is to minimize the total cost, which consists of the relocation cost of facilities and the distance cost of requests to their nearest facilities. We provide a lower bound for the OMFL problem that even holds on <jats:italic>uniform metrics<\/jats:italic>. A natural approach to solve the OMFL problem for general metric spaces is to utilize <jats:italic>hierarchically well-separated trees<\/jats:italic> (HSTs) and directly solve the OMFL problem on HSTs. In this paper, we provide the first step in this direction by solving a <jats:italic>generalized variant<\/jats:italic> of the OMFL problem on uniform metrics that we call G-OMFL. We devise a simple deterministic online algorithm and provide a tight analysis for the algorithm. The second step remains an open question. Inspired by the <jats:italic>k<\/jats:italic>-server problem, we introduce a new variant of the OMFL problem that focuses solely on minimizing movement cost. We refer to this variant as M-OMFL. Additionally, we provide a lower bound for M-OMFL that is applicable even on uniform metrics.<\/jats:p>","DOI":"10.1007\/s00224-023-10145-9","type":"journal-article","created":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T07:01:59Z","timestamp":1696575719000},"page":"1268-1306","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Toward Online Mobile Facility Location on General Metrics"],"prefix":"10.1007","volume":"67","author":[{"given":"Abdolhamid","family":"Ghodselahi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,6]]},"reference":[{"key":"10145_CR1","doi-asserted-by":"publisher","unstructured":"Ghodselahi, A., Kuhn, F.: Serving online requests with mobile servers. In: Elbassioni, K., Makino, K. (eds.) Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), vol. 9472, pp. 740\u2013751. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_62","DOI":"10.1007\/978-3-662-48971-0_62"},{"key":"10145_CR2","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Hajiaghayi, M., Mahini, H., Sayedi-Roshkhar, A.S., Oveisgharan, S., Zadimoghaddam, M.: Minimizing movement. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 258\u2013267 (2007). https:\/\/doi.org\/10.1145\/1541885.1541891","DOI":"10.1145\/1541885.1541891"},{"key":"10145_CR3","doi-asserted-by":"publisher","unstructured":"Friggstad, Z., Salavatipour, M.R.: Minimizing movement in mobile facility location problems. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 357\u2013366 (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.12","DOI":"10.1109\/FOCS.2008.12"},{"key":"10145_CR4","doi-asserted-by":"publisher","unstructured":"Devanur, N., Garg, N., Khandekar, R., Pandit, V., Saberi, A., Vazirani, V.: Price of anarchy, locality gap, and a network service provider game. In: Proceedings of the 1st International Workshop on Internet and Network Economics (WINE), pp. 1046\u20131055 (2005). https:\/\/doi.org\/10.1007\/11600930_105","DOI":"10.1007\/11600930_105"},{"key":"10145_CR5","doi-asserted-by":"publisher","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proceedings of the 33rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 21\u201329 (2001). https:\/\/doi.org\/10.1145\/380752.380755","DOI":"10.1145\/380752.380755"},{"key":"10145_CR6","doi-asserted-by":"publisher","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 731\u2013740 (2002). https:\/\/doi.org\/10.1145\/509907.510012","DOI":"10.1145\/509907.510012"},{"key":"10145_CR7","unstructured":"Drezner, Z., Hamacher, H.W.: Facility Location: Applications and Theory, (2004)"},{"key":"10145_CR8","unstructured":"Black, D.L., Sleator, D.D.: Competitive Algorithms for Replication and Migration Problems, (1989)"},{"key":"10145_CR9","doi-asserted-by":"publisher","unstructured":"Meyerson, A.: Online facility location. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 426\u2013431 (2001). https:\/\/doi.org\/10.1109\/SFCS.2001.959917","DOI":"10.1109\/SFCS.2001.959917"},{"key":"10145_CR10","doi-asserted-by":"publisher","unstructured":"Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for on-line problems. In: Proceedings of the 20th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 322\u2013333 (1988). https:\/\/doi.org\/10.1145\/62212.62243","DOI":"10.1145\/62212.62243"},{"key":"10145_CR11","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM. 28, 202\u2013208 (1985). https:\/\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM."},{"key":"10145_CR12","doi-asserted-by":"publisher","first-page":"2898","DOI":"10.1007\/s00453-022-00993-1","volume":"84","author":"B De Keijzer","year":"2022","unstructured":"De Keijzer, B., Wojtczak, D.: Facility reallocation on the line. Algorithmica. 84, 2898\u20132925 (2022). https:\/\/doi.org\/10.1007\/s00453-022-00993-1","journal-title":"Algorithmica."},{"key":"10145_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2021.01.028","volume":"858","author":"D Fotakis","year":"2021","unstructured":"Fotakis, D., Kavouras, L., Kostopanagiotis, P., Lazos, P., Skoulakis, S., Zarifis, N.: Reallocating multiple facilities on the line. Theor. Comput. Sci. (TCS) 858, 13\u201334 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.01.028","journal-title":"Theor. Comput. Sci. (TCS)"},{"key":"10145_CR14","doi-asserted-by":"publisher","unstructured":"Feldkord, B., Knollmann, T., Meyer auf der Heide, F.:Online facility location with mobile facilities. Theor. Comput. Sci. (TCS) 907, 45\u201361 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.01.019","DOI":"10.1016\/j.tcs.2022.01.019"},{"key":"10145_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3364204","volume":"6","author":"B Feldkord","year":"2019","unstructured":"Feldkord, B., Der Heide, F.M.A.: The mobile server problem. ACM Trans. Parallel. Comput. (TOPC) 6, 1\u201317 (2019). https:\/\/doi.org\/10.1145\/3364204","journal-title":"ACM Trans. Parallel. Comput. (TOPC)"},{"key":"10145_CR16","doi-asserted-by":"publisher","unstructured":"Feldkord, B., Knollmann, T., Malatyali, M., Meyer auf der Heide, F.: Managing multiple mobile resources. In: Proceedings of the 17th International Workshop on Approximation and Online Algorithms (WAOA), pp. 120\u2013137 (2019). https:\/\/doi.org\/10.1007\/s00224-020-10023-8","DOI":"10.1007\/s00224-020-10023-8"},{"key":"10145_CR17","doi-asserted-by":"publisher","first-page":"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. Algorithm. (TALG) 15, 1\u201321 (2019). https:\/\/doi.org\/10.1145\/3340296","journal-title":"ACM Trans. Algorithm. (TALG)"},{"key":"10145_CR18","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1137\/S0097539791199796","volume":"23","author":"J Westbrook","year":"1994","unstructured":"Westbrook, J.: Randomized algorithms for multiprocessor page migration. SIAM J. Comput. 23, 951\u2013965 (1994). https:\/\/doi.org\/10.1137\/S0097539791199796","journal-title":"SIAM J. Comput."},{"key":"10145_CR19","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. (TCS) 268, 43\u201366 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00259-0","journal-title":"Theor. Comput. Sci. (TCS)"},{"key":"10145_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s00450-011-0150-8","volume":"27","author":"M Bienkowski","year":"2012","unstructured":"Bienkowski, M.: Migrating and replicating data in networks. Comput. Sci-Res. & Dev. 27, 169\u2013179 (2012). https:\/\/doi.org\/10.1007\/s00450-011-0150-8","journal-title":"Comput. Sci-Res. & Dev."},{"key":"10145_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9049-y","volume":"50","author":"D Fotakis","year":"2008","unstructured":"Fotakis, D.: On the competitive ratio for online facility location. Algorithmica. 50, 1\u201357 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9049-y","journal-title":"Algorithmica."},{"key":"10145_CR22","doi-asserted-by":"publisher","unstructured":"Fotakis, D.: Incremental algorithms for facility location and k-median. In: Albers, S., Radzik, T. (eds.) Proceedings of the 12th Annual European Symposium on Algorithms (ESA), vol. 3221, pp. 347\u2013358. Springer, Berlin, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30140-0_32","DOI":"10.1007\/978-3-540-30140-0_32"},{"key":"10145_CR23","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1145\/1959045.1959065","volume":"42","author":"D Fotakis","year":"2011","unstructured":"Fotakis, D.: Online and incremental algorithms for facility location. ACM SIGACT News. 42, 97\u2013131 (2011). https:\/\/doi.org\/10.1145\/1959045.1959065","journal-title":"ACM SIGACT News."},{"key":"10145_CR24","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s10100-010-0153-8","volume":"19","author":"G Div\u00e9ki","year":"2011","unstructured":"Div\u00e9ki, G., Imreh, C.: Online facility location with facility movements. CEJOR. 19, 191\u2013200 (2011). https:\/\/doi.org\/10.1007\/s10100-010-0153-8","journal-title":"CEJOR."},{"key":"10145_CR25","doi-asserted-by":"publisher","unstructured":"Cot\u00e9, A., Meyerson, A., Poplawski, L.: Randomized k-server on hierarchical binary trees. In: Proceedings of the 40th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 227\u2013234 (2008). https:\/\/doi.org\/10.1145\/1374376.1374411","DOI":"10.1145\/1374376.1374411"},{"key":"10145_CR26","doi-asserted-by":"publisher","unstructured":"Bansal, N., Buchbinder, N., Madry, A., Naor, J.S.: A polylogarithmic-competitive algorithm for the k-server problem. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 267\u2013276 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.63","DOI":"10.1109\/FOCS.2011.63"},{"key":"10145_CR27","doi-asserted-by":"publisher","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 448\u2013455 (2003). https:\/\/doi.org\/10.1145\/780542.780608","DOI":"10.1145\/780542.780608"},{"key":"10145_CR28","doi-asserted-by":"publisher","unstructured":"Ghodselahi, A., Kuhn, F.: Dynamic analysis of the arrow distributed directory protocol in general networks. In: Richa, A.W. (ed.) Proceedings of the 31st International Symposium on Distributed Computing (DISC), vol. 91, pp. 22\u201312216. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.22","DOI":"10.4230\/LIPIcs.DISC.2017.22"},{"key":"10145_CR29","doi-asserted-by":"publisher","unstructured":"Azar, Y., Ganesh, A., Ge, R., Panigrahi, D.: Online service with delay. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 551\u2013563 (2017). https:\/\/doi.org\/10.1145\/3055399.3055475","DOI":"10.1145\/3055399.3055475"},{"key":"10145_CR30","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1002\/net.10080","volume":"42","author":"MT Hajiaghayi","year":"2003","unstructured":"Hajiaghayi, M.T., Mahdian, M., Mirrokni, V.S.: The facility location problem with general cost functions. Netw. 42, 42\u201347 (2003). https:\/\/doi.org\/10.1002\/net.10080","journal-title":"Netw."},{"key":"10145_CR31","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. (JACM) 42, 971\u2013983 (1995). https:\/\/doi.org\/10.1145\/210118.210128","journal-title":"J. ACM. (JACM)"},{"key":"10145_CR32","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. Algorithm. 12, 685\u2013699 (1991). https:\/\/doi.org\/10.1016\/0196-6774(91)90041-V","journal-title":"Competitive paging algorithms. J. Algorithm."},{"key":"10145_CR33","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. Algorithm. 11, 208\u2013230 (1990). https:\/\/doi.org\/10.1016\/0196-6774(90)90003-W","journal-title":"J. Algorithm."},{"key":"10145_CR34","doi-asserted-by":"publisher","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 184\u2013193 (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548477","DOI":"10.1109\/SFCS.1996.548477"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10145-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10145-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10145-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T01:03:30Z","timestamp":1701997410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10145-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,6]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10145"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10145-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,10,6]]},"assertion":[{"value":"20 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Informed consent was obtained from all individual participants included in the study","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"The participants have consented to the submission of the case report to the journal","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors have no relevant financial or non-financial interests to disclose","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest\/Competing interests"}}]}}