A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

被引：13
作者：
Donglei Du
Ruixing Lu
Dachuan Xu
机构：
[1] University of New Brunswick,Faculty of Business Administration
[2] Beijing University of Technology,Department of Applied Mathematics
来源：
Algorithmica | 2012年 / 63卷
关键词：
Facility location problem; Approximation algorithm; Submodular function;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.
引用
收藏
页码：191 / 200
页数：9
相关论文
共 42 条
[1]  
Aardal K.I.(1999)A 3-approximation algorithm for the Inf. Process. Lett. 72 161-167
[2]  
Chudak F.A.(2003)-level uncapacitated facility location problem SIAM J. Discrete Math. 18 207-217
[3]  
Shmoys D.B.(2010)Improved combinatorial approximation algorithms for the SIAM J. Comput. 39 2212-2231
[4]  
Ageev A.(2003)-level facility location problem SIAM J. Comput. 33 1-25
[5]  
Ye Y.(2010)An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem J. Comb. Optim. 20 361-368
[6]  
Zhang J.(2003)Improved approximation algorithms for the uncapacitated facility location problem Discrete Appl. Math. 131 311-322
[7]  
Byrka J.(1999)An approximation algorithm for the J. Algorithms 31 228-248
[8]  
Aardal K.I.(2001)-level capacitated facility location problem J. ACM 48 274-296
[9]  
Chudak F.A.(2003)A push-relabel framework for submodular function minimization and applications to parametric optimization J. ACM 50 795-824
[10]  
Shmoys D.B.(2000)Greedy strikes back: improved facility location algorithms J. Algorithms 37 146-188
12345