Approximating $k$-Median via Pseudo-Approximation

• DOI: 10.48550/arxiv.1211.0243
• Publication Date: 2012-01-01
• Authors: Li Shi; Ola Svensson
• Keywords: Born–Huang approximation; Alpha (finance); Approximation Theory; Orders of approximation

We present a novel approximation algorithm for $k$-median that achieves an guarantee of $1+\sqrt{3}+\epsilon$, improving upon the decade-old ratio $3+\epsilon$. Our approach is based on two components, each which, we believe, independent interest. First, show in order to give $\alpha$-approximation $k$-median, it sufficient \emph{pseudo-approximation algorithm} finds $\alpha$-approximate solution by opening $k+O(1)$ facilities. This rather surprising result as there exist instances which $k+1$ facilities may lead significant smaller cost than if only $k$ were opened. Second, such pseudo-approximation with $\alpha= 1+\sqrt{3}+\epsilon$. Prior our work, was not even known whether $k + o(k)$ would help improve ratio.