Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation
Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation
复制标题
DOI：
10.1145/375827.375845
复制
发表时间：
2001-03
期刊：
影响因子：
--
通讯作者：
K. Jain;V. Vazirani
中科院分区：
文献类型：
--
作者：
K. Jain;V. Vazirani
我们提出了近似算法的度量无容量限制的设施选址问题和度量k-中位数问题分别实现3和6的保证。我们的算法的显着特点是它们的低运行时间：O（mlogm）和O（mlogm（L + log（n），其中n和m是在城市和设施的基本完全二部图的顶点和边的总数分别。主要的算法思想是一个新的扩展的原始-对偶模式和使用拉格朗日松弛推导近似算法。
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m logm) and O(m logm(L + log (n))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.