Approximating k-median via pseudo-approximation

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + √3 + ε, improving upon the decade-old ratio of 3+ε. 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 α-approximation algorithm for k-median, it is sufficient to give a pseudo- approximation algorithm that finds an α-approximate solu- tion by opening k+O(1) facilities. This is a rather surprising result as there exist instances for which opening k + 1 facil- ities may lead to a significant smaller cost than if only k facilities were opened. Second, we give such a pseudo-approximation algorithm with α = 1+ √3+ε. Prior to our work, it was not even known whether opening k + o(k) facilities would help improve the approximation ratio. Copyright 2013 ACM.

Published in:
Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13, 901-910
Presented at:
the 45th annual ACM symposium, Palo Alto, California, USA, 01-04 06 2013
New York, New York, USA, ACM Press

 Record created 2015-08-28, last modified 2018-01-28

Rate this document:

Rate this document:
(Not yet reviewed)