A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties

作者：Li, Yu; Du, Donglei; Xiu, Naihua; Xu, Dachuan^*

来源：Theoretical Computer Science, 2013, 476: 109-117.

DOI：10.1016/j.tcs.2012.11.037

• Approximation algorithm
• Facility location problem
• Linear programming
• Submodular function

We offer the currently best approximation ratio 2.375 for the facility location problem with submodular penalties (FLPSP), improving not only the previous best combinatorial ratio 3, but also the previous best non-combinatorial ratio 2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique.

• 出版日期2013-3-11
• 单位北京交通大学; 北京工业大学