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