满足参数不等式的k-Center问题的近似算法

Approximation algorithms for k-Center problem with aparameterized triangle inequality

考虑了无向完全图中满足参数不等式的k-Center问题,确切来讲,假定有一参数τ满足τ≥12,对于任意3个点x,y和z,都有dist(x,y)≤τ(dist(x,z)+dist(z,y)).利用罚参数中技术得到了1个2τ近似的算法,并且证明了对任意的ε>0,不存在2τ-ε近似,除非P=NP.用同样的技术得到了对于有权重限制的k-Center问题的1个2τ2+τ近似算法.

The approximate algorithm for k-Center problem in complete undirected graphs with a parameterized triangle inequality was considered.Assume that for some parameter τ≥12,the distances satisfy the triangle inequality dist(x,y)≤τ(dist(x,z)+dist(z,y)) for every triple of vertices x,y,and z.A 2τ-approximation algorithm was obtained and proved that it is the best one.Subsequently,a 2τ~2+τ-approximation algorithm for the weighted version was obtained.