Online facility location with mobile facilities

We examine the Online Facility Location problem in an extended version. Fotakis showed a lower bound of Omega(log n/log log n) for the original Online Facility Location problem, where n is the number of clients. This bound holds even on the real line and for randomized algorithms against oblivious adversaries. We propose randomized online algorithms in the following setting: We consider the Euclidean space of arbitrary dimension and allow the facilities to either move arbitrarily or to move at most a constant distance m in each time step. The costs for moving a facility from a to b is D . d(a, b) where D >= 1 is a constant. Clients are assigned to facilities instantly and irreversibly. The cost for serving the clients is either calculated as soon as a client arrives or at the end of the computation. The algorithms for these two cost models achieve the same competitiveness on the line, which, in contrast to the original Online Facility Location problem, is independent of n. In the case of arbitrary movement, it only depends on D. In the case of a limited movement distance m, it additionally depends on m and the opening costs of the facilities. We show that our results are asymptotically tight on the real line. For the Euclidean space of higher dimensions, we give an algorithm for the model where costs for clients are evaluated immediately. The competitive ratio of our algorithm depends on the above parameters and additionally on the number of optimal facilities. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

The study investigates the extended version of the Online Facility Location problem and proposes randomized online algorithms for different parameter settings. The algorithms achieve competitiveness independent of the number of clients n on the line, depending only on a constant D in the case of arbitrary movement and additionally on the movement distance m and opening costs of facilities in the case of limited movement.