  We study the multistage $K$-facility reallocation problem on the real line,
where we maintain $K$ facility locations over $T$ stages, based on the
stage-dependent 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, 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.
