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

Abstract

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

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.

References

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]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[3]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[4]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[5]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[6]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[7]	CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong. Approximation algorithms for two-machine flow shop scheduling with an outsourcing option [J]. Operations Research Transactions, 2016, 20(4): 109-114.
[8]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[9]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[10]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[11]	YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi. An approximation algorithm for reliable facility location problem [J]. Operations Research Transactions, 2015, 19(4): 14-24.
[12]	FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine [J]. Operations Research Transactions, 2015, 19(3): 116-122.
[13]	WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing. Approximation algorithms for the priority facility location problem with submodular penalties [J]. Operations Research Transactions, 2015, 19(2): 1-14.
[14]	XU Dachuan, WAN Wei, WU Chenchen, XU Wenqing. A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem [J]. Operations Research Transactions, 2014, 18(2): 17-28.
[15]	LI Zhening, LING Chen, WANG Yiju, YANG Qingzhi. Some advances in tensor analysis and polynomial optimization [J]. Operations Research Transactions, 2014, 18(1): 134-148.

Bicriteria approximation algorithms for the lower-bounded facility location problem with penalties and soft-capacity

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments