A Better-than-$2$ Approximation for $k$-Median Part II: Stable Instances

Abstract

We consider the $k$-median problem on general metric spaces, subject to the condition that the instances are $\beta$-stable (i.e., the optimal solution using $k-1$ centers has a cost at least $(1+\beta)$ times that of the optimal solution with $k$ centers). We give a $(1.89+\epsilon)$-approximation algorithm for such instances running in time $\exp(1/(\beta \times \mathrm{poly}(\epsilon)))\cdot \mathrm{poly}_{\epsilon}(n)$. In particular, for $\beta =\mathrm{poly}(\epsilon)/\log n$ and $\epsilon$ a tiny constant, this is a polynomial-time algorithm. This improves on previous work showing a $(2 + \epsilon)$-approximation algorithm with similar running time [CGL+25]. Combined with the pseudo-approximation algorithm in our companion work, this results in a better-than-$2$ approximation algorithm for general $k$-median instances. Our main technical contribution is a novel nuanced analysis of local search that allows us to isolate a subset of clients on which we lose essentially nothing compared to the optimal solution, while losing an approximation factor of $3$ on the rest of the clients. We complement this with an algorithm based on sampling and partial enumeration, achieving a better-than-$2$ approximation on the rest of the clients. Trading off these two algorithms yields our final approximation.