APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + root 3 + epsilon, improving upon the decade-old ratio of 3 + epsilon. Our improved approximation ratio is achieved by exploiting the power of pseudo-approximation. More specifically, 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 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 significantly smaller cost than that of opening only k facilities. Second, we give such a pseudo-approximation algorithm with alpha = 1 + root 3 + epsilon. Prior to our work, it was not even known whether opening k + o(k) facilities would help improve the approximation ratio.


Published in:
Siam Journal On Computing, 45, 2, 530-547
Presented at:
45th Annual ACM Symposium on the Theory of Computing (STOC), Palo Alto, CA, JUN 01-04, 2013
Year:
2016
Publisher:
Philadelphia, Siam Publications
ISSN:
0097-5397
Keywords:
Laboratories:




 Record created 2016-07-19, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)