An improved approximation algorithm for k-Median

Abstract

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 $\hat{I}\pm <1+2\ln (n/k)$. That is, it guarantees a solution having size at most $\hat{I}\pm \times k$, and cost at most the cost of any size-$k$ solution. This is the first polynomial-time approximation algorithm to match the well-known bounds of $H_{\hat{I}}”$ and $1+\ln (n/k)$ for unweighted Set Cover (a special case) within a constant factor. It matches these bounds within a factor of 2. The algorithm runs in time $O(km\log (n/k)\log m)$, where $n$ is the number of customers and $m$ is the instance size.