Henry L. Fleischmann

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

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 i...