Approximation algorithms for metric facility location and <i>k</i> -Median problems using the primal-dual schema and Lagrangian relaxation 论文
2001Journal of the ACM引用 813
Facility Location and Emergency ManagementComplexity and Algorithms in GraphsVehicle Routing Optimization Methods
详细信息
- 发表期刊/会议
- Journal of the ACM
- 发表日期
- 2001-03-01
- 发表年份
- 2001
关键词
Facility Location and Emergency ManagementComplexity and Algorithms in GraphsVehicle Routing Optimization Methods
摘要
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 log m ) and O(m log m(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.