Abstract
We study the multistage K-facility reallocation
problem on the real line, where we maintain K facility locations over T stages, based on the stagedependent locations of n agents. Each agent is connected to the nearest facility at each stage, and the
facilities may move from one stage to another, to
accommodate different agent locations. The objective is to minimize the connection cost of the
agents plus the total moving cost of the facilities,
over all stages. K-facility reallocation was introduced by [de Keijzer and Wojtczak, 2018], where
they mostly focused on the special case of a single
facility. Using an LP-based approach, we present a
polynomial time algorithm that computes the optimal solution for any number of facilities. We also
consider online K-facility reallocation, where the
algorithm becomes aware of agent locations in a
stage-by-stage fashion. By exploiting an interesting
connection to the classical K-server problem, we
present a constant-competitive algorithm for K = 2
facilities