We shall discuss a new LP-rounding algorithm for facility location problems. The algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood.
The use of exponential clocks gives rise to several properties that distinguish our approach from previous roundings for facility location problems. In particular, we use no clustering and we allow clients to connect through paths of arbitrary lengths.
These properties lead to an algorithm that is ``stable'' with respect to small perturbations in the LP-solution which is crucial for obtaining the first constant approximation algorithm for the dynamic facility location problem: a generalization proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of temporally evolving social/infrastructure networks.