带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究

摘要/Abstract

摘要： 研究带惩罚和软容量约束的下界设施选址问题. 扩展Guha等(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)和Karger等(Karger D R, Minkoff M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329)的工作到带有惩罚的下界约束设施选址问题，提出了一个新的双标准近似算法，得到了同样的近似比ρ(1+α)/(1-α). 进一步考虑带惩罚和软容量约束的下界设施选址问题，得到了近似比为2ρ(1+α)/(1-α)的双标准近似算法.

关键词: 下界约束设施选址, 近似算法, 双标准算法

Abstract: We study the lower-bounded facility location problem with penalties (LBFLP) and the soft-capacity LBFLP. For the LBFLP, we present an updated bicriteria approximation algorithm which maintains the same performance factor ρ(1+α)/(1-α) as that for the problem without penalties in Hierarchical placement and network design problems(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)and Building steiner trees with incomplete global knowledge(Karger D R, Minkoff M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329). We further extend this result to the soft-capacitated LBFLP and achieve a performance factor twice as much as that for LBFLP.

Key words: lower-bounded facility location, approximation algorithm, bicriteria algorithm

李改弟，王真，吴裕林. 带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究[J]. 运筹学学报, 2013, 17(1): 117-126.

LI Gaidi, WANG Zhen, WU Yulin. Bicriteria approximation algorithms for the lower-bounded facility location problem with penalties and soft-capacity[J]. Operations Research Transactions, 2013, 17(1): 117-126.

参考文献

Du D L, Lu R X, Xu D C. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmic, 2012, 63: 191-200.
Du D L, Wang X, Xu D C. An approximation algorithm for the k-level capacitated facility location problem [J]. Journal of Combinatorial Optimization, 2010, 20: 361-368.
Shu J. An efficient greedy heuristic for warehouse-retailer network design optimization [J].   Transportation Science, 2010, 44: 183-192.
Shu J, Teo C P, Max Shen Z J. Stochastic transportation-inventory network design problem [J]. Operations Research, 2005, 53: 48-60.
Teo C P,   Shu J. Warehouse-retailer network design problem [J]. Operations Research, 2004, 52: 396-408.
Xu D C, Du D L. The k-level facility location game [J]. Operations Research Letters, 2006, 34: 421-426.
Xu D C, Zhang S Z. Approximation algorithm for facility location with service installation costs [J]. Operations Research Letters, 2008,   36: 46-50.
Zhang J W. Approximating the two-level facility location problem via a quasi-greedy approach [J]. Mathematical Programming, 2006, 108: 159-176.
Zhang J W, Chen B,   Ye Y Y. A multiexchange local search algorithm for the capacitated facility location problem [J]. Mathematics of Operations Research, 2005, 30: 389-403.
Zhang P. A new approximation algorithm for the k-facility location problem [J].   Theoretical Computer Science, 2007, 384: 126-135.
Shmoys D B, Tardos E, Aardal K I. Approximation algorithms for facility location problems [C]// Proceedings of STOC, New York: Association for Computing Machinery, 1997.
Li S.   A 1.488-approximation algorithm for the uncapacitated facility location problem [J]. Proceedings of ICALP, Part II, 2010, 77-88.
Byrka J, Aardal K I. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem [J].   SIAM Journal on Computing, 2010, 39: 2212-2231.
Guha S, Khuller S. Greedy strikes back: improved facility location algorithms [J]. Proceedings of SODA, 1998, 649-657.
Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]// Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328.
Karger D R, Minkoff M. Building steiner trees with incomplete global knowledge [C]// Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329.
Svitkina Z. Lower-bounded facility location [J]. Journal ACM Transactions on Algorithms, 2010,   69: 1-16.
Svitkina Z. Lower-bounded facility location [J]. Journal ACM Transactions on Algorithms, 2010, 69: 1-16.
Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problems with outliers [C/OL]// Proceedings of SODA, 2001[2011-08-20], http://dl.acm.org/citation.cfm.
Xu G, Xu J. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties [J].   Information Processing Letters, 2005, 94: 119-123.
Xu G, Xu J. An improved approximation algorithm for uncapacitated facility location problems with penalties [J].   Journal of Combinatorial Optimization, 2009, 17: 424-436.
Chudak F, Shmoys D B. Improved approximation algorithms for a capacitated facility location problem [C]// Proceedings of SODA, Berlin: Springer, 1999.
Jain K, Vazirani V V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J]. Journal of the ACM, 2001, 48: 274-296.
Mahdian M, Ye Y Y, Zhang J W. Approximation algorithms for metric facility location problems [J]. SIAM Journal on Computing, 2006, 36: 411-432.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[3]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[4]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[5]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[6]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[7]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[8]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[9]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[10]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[11]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[12]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.
[13]	范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.
[14]	王颖, 王凤敏, 徐大川, 徐文青. 带次模惩罚的优先设施选址问题的近似算法[J]. 运筹学学报, 2015, 19(2): 1-14.
[15]	徐大川, 万玮, 吴晨晨, 徐文青. 随机容错设施选址问题的原始-对偶近似算法[J]. 运筹学学报, 2014, 18(2): 17-28.