Approximating k-median via pseudo-approximation

From MaRDI portal
Publication:2805513

DOI10.1137/130938645zbMATH Open1338.90346arXiv1211.0243OpenAlexW2343942810MaRDI QIDQ2805513FDOQ2805513


Authors: Shi Li, Ola Svensson Edit this on Wikidata


Publication date: 12 May 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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


Full work available at URL: https://arxiv.org/abs/1211.0243




Recommendations




Cites Work


Cited In (48)





This page was built for publication: Approximating \(k\)-median via pseudo-approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805513)