An improved approximation algorithm for k-Median

Neal E. Young

We give a polynomial-time approximation algorithm for the (not necessarily metric) $k$-Median problem. The algorithm is an $\hat{I}\pm$-size-approximation algorithm for $α< 1 + 2 \ln(n/k)…