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

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/

https://www.ort.shu.edu.cn/EN/Y2013/V17/I1/117

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]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[2]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[3]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[4]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[5]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[6]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[7]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[8]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[9]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[10]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[11]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[12]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[13]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[14]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[15]	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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments