{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:26:13Z","timestamp":1773325573912,"version":"3.50.1"},"reference-count":11,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T00:00:00Z","timestamp":1614211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called \u201cevolving metrics\u201d, thus Dynamic Facility Location can be alternatively interpreted as a Facility Location problem in evolving metrics. The objective in this time-dependent variant is to balance the trade-off between optimizing the classic objective function and the stability of the solution, which is modeled by charging a switching cost when a client\u2019s assignment changes from one facility to another. In this paper, we study the online variant of Dynamic Facility Location. We present a randomized O(logm+logn)-competitive algorithm, where m is the number of facilities and n is the number of clients. In the first step, our algorithm produces a fractional solution, in each timestep, to the objective of Dynamic Facility Location involving a regularization function. This step is an adaptation of the generic algorithm proposed by Buchbinder et al. in their work \u201cCompetitive Analysis via Regularization.\u201d Then, our algorithm rounds the fractional solution of this timestep to an integral one with the use of exponential clocks. We complement our result by proving a lower bound of \u03a9(m) for deterministic algorithms and lower bound of \u03a9(logm) for randomized algorithms. To the best of our knowledge, these are the first results for the online variant of the Dynamic Facility Location problem.<\/jats:p>","DOI":"10.3390\/a14030073","type":"journal-article","created":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T21:16:53Z","timestamp":1614287813000},"page":"73","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Online Facility Location in Evolving Metrics"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6864-8960","authenticated-orcid":false,"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[{"name":"School of Electrical and Computer Engineering, National Technical University of Athens, 15780 Athens, Greece"}]},{"given":"Loukas","family":"Kavouras","sequence":"additional","affiliation":[{"name":"School of Electrical and Computer Engineering, National Technical University of Athens, 15780 Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9258-6798","authenticated-orcid":false,"given":"Lydia","family":"Zakynthinou","sequence":"additional","affiliation":[{"name":"Khoury College of Computer Science, Northeastern University, Boston, MA 02115, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Meyerson, A. (2001, January 14\u201317). Online Facility Location. Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, USA.","DOI":"10.1109\/SFCS.2001.959917"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/j.tcs.2006.05.015","article-title":"Incremental algorithms for Facility Location and K-Median","volume":"361","author":"Fotakis","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Esparza, J., Fraigniaud, P., Husfeldt, T., and Koutsoupias, E. (2014). Facility Location in Evolving Metrics. Automata, Languages, and Programming, Proceedings of the 41st International Colloquium (ICALP 2014), Copenhagen, Denmark, 8\u201311 July 2014, Springer. Part II.","DOI":"10.1007\/978-3-662-43951-7"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01581035","article-title":"Heuristics for the fixed cost median problem","volume":"22","author":"Hochbaum","year":"1982","journal-title":"Math. Program."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","article-title":"Greedy Strikes Back: Improved Facility Location Algorithms","volume":"31","author":"Guha","year":"1999","journal-title":"J. Algorithms"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","article-title":"A 1.488 approximation algorithm for the uncapacitated facility location problem","volume":"222","author":"Li","year":"2013","journal-title":"Inf. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-9049-y","article-title":"On the Competitive Ratio for Online Facility Location","volume":"50","author":"Fotakis","year":"2008","journal-title":"Algorithmica"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.ic.2004.06.002","article-title":"A simple and deterministic competitive algorithm for online facility location","volume":"194","author":"Anagnostopoulos","year":"2004","journal-title":"Inf. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"21:1","DOI":"10.1145\/2928272","article-title":"Dynamic Facility Location via Exponential Clocks","volume":"13","author":"An","year":"2017","journal-title":"ACM Trans. Algorithms"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Chen, S., and Naor, J. (2014, January 5\u20137). Competitive Analysis via Regularization. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.32"},{"key":"ref_11","unstructured":"Borodin, A., and El-Yaniv, R. (1998). Online Computation and Competitive Analysis, Cambridge University Press."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/73\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:28:41Z","timestamp":1760160521000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,25]]},"references-count":11,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030073"],"URL":"https:\/\/doi.org\/10.3390\/a14030073","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,25]]}}}