Dynamic High-Dimensional Facility Location with Low Recourse

We study the problem of dynamic facility location with non-uniform costs. Facility location is a central problem in unsupervised learning and in recent years the dynamic version of the problem has been extensively studied. In this paper, we study the setting where clients are added and deleted in real-time and one is interested in maintaining efficiently a stable and high-quality solution. Interestingly, we are able to show that on High Dimensional Euclidean metrics it is possible to obtain efficient algorithms for this problem. More formally, we obtain a randomized algorithm for dynamic facility location in $d$-dimensional Euclidean spaces with $\gamma$ approximation ratio, $O(\log m)$ amortized recourse and $\text{poly}(d) \cdot (m+n)^{O(1/\gamma)}$ amortized update time, for every sufficiently large constant $\gamma \geq 1$. Our result is the first efficient dynamic algorithm for the non-uniform dynamic facility location problem in high-dimensional Euclidean spaces. It also provides a stronger recourse bound than the existing solutions.