Approximating k-median via pseudo-approximation
Approximating k-median via pseudo-approximation
复制标题
DOI：
10.1145/2488608.2488723
复制
发表时间：
2012-11
期刊：
影响因子：
--
通讯作者：
Shi Li;O. Svensson
中科院分区：
文献类型：
--
作者：
Shi Li;O. Svensson
我们提出了一种新的k-Medium的近似算法，该算法在十年前3+√的基础上得到了1+ε+ε的近似保证。我们的方法基于两个组成部分，我们认为每个组成部分都具有独立的利益。首先，我们证明了为了给出k-中位数的α逼近算法，只要给出一个伪逼近算法就足够了，该伪逼近算法通过开放k+O(1)设施来寻找α-逼近解。这是一个相当令人惊讶的结果，因为存在这样的情况：与只开放k个设施相比，开放k+1个设施可能会产生显著更小的成本。其次，给出了α=1+√3+ε的伪逼近算法。在我们的工作之前，甚至不知道开放k+o(K)设施是否有助于提高近似比。
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 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 α= 1+√3+ε. Prior to our work, it was not even known whether opening k + o(k) facilities would help improve the approximation ratio.