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 \emph{non-uniform} dynamic facility location problem in high-dimensional Euclidean spaces. It also provides a stronger recourse bound than the existing solutions.

Imagine trying to place computer servers to efficiently serve a shifting group of users, where each server location has a different setup cost. In machine learning, this "facility location" problem is applied to discover core groups, or clusters, in complex, evolving datasets. As new data arrives or old data is deleted, we want an algorithm that updates these cluster centers quickly and accurately. However, we must also avoid chaotic ripple effects where one small data change forces the system to drastically reassign most users to new servers. Our paper presents the first efficient algorithm to solve this problem for high-dimensional data with variable setup costs. Instead of relying on rigid distance rules, our method uses a flexible, hierarchical grouping strategy. We pair this with fast geometric search tools that seamlessly maintain a near-optimal arrangement of facilities and users over time. Crucially, our algorithm guarantees stability, ensuring that only a tiny fraction of existing connections ever need to be reshuffled when the network changes. This allows real-world systems and dynamic networks to adapt to new information in real time, without wasting computational power or causing widespread disruptions.