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

Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6

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 a…