A local, distributed constant-factor approximation algorithm for the dynamic facility location problem

摘要

We present a distributed, local solution to the dynamic facility location problem in general metrics, where each node is able to act as a facility or a client. To decide which r ole it should take, each node keeps up a simple invariant in its local neighborhood. This guarantees a global constant factor approximation when the invariant is satisfied at all nodes. Due to the changing distances between nodes, invariants can be violated. We show that restoring the invariants is bounded to a constant neighborhood, takes logarithmic (in the number of nodes) asynchronous rounds and affects each node at most twice per violation.