带次模惩罚的优先设施选址问题的近似算法

doi:10.15960/j.cnki.issn.1007-6093.2015.02.001

Abstract

Abstract:

In this paper, we study priority facility location problem with submodular penalties where each client has a level-of-service requirement. An open facility must satisfy the requirement of the clients served by it, and there is a submodular penalty cost corresponding with the unserved clients. The objective is to minimize the sum of the opening cost, the connection cost and the submodular penalty cost. We present the integer program, the linear programming relaxation and the dual program for the problem. Using the primal-dual and greedy augmentation techniques, we then propose two approximation algorithms and obtain the approximation ratios of 3 and 2.375 respectively.

Key words: submodular penalties, priority facility location, primal-dual, greedy augmentation, approximation algorithm

WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing. Approximation algorithms for the priority facility location problem with submodular penalties[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2015.02.001.

References

Shmoys D B, Tard\ddot{o}s \'{E}, Aardal K I. Approximation algorithms for facility location problems [C]//Proceedings of STOC, New York: ACM, 1997, 265-274.

Jain K, Mahdian M, Saberi A. A new greedy approach for facility location problems [C]// Proceedings of the 34th ACM Symposium on Theory of Computing, New York: Association for Computing Machinery, 2002, 731-740.

Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [C]//Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part II, Springer, LNCS 6756, 2011, 77-88.

Jain K, Vazirani V V. Primal-dual 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.

Guha S, Khuller S. Greedy strike back: Improved facility location algorithms [J]. Journal of Algorithms, 1999, 31: 228-248.

Charikar M, Guha S. Improved combinatorial algorithms for facility location problems [J]. SIAM Journal on Computing, 2005, 34: 803-824.

Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problems with outliers [C]// Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2001, 642-651.

Chudak F A, Nagano K. Efficient solutions to relaxations of combinatorial problems with submodular penalties via the lovasz extension and non-smooth convex optimization [C]//Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2007, 79-88.

Hayrapetyan A, Swamy C, Tard\ddot{o}s \'{E}. Network design for information networks [C]// Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2005, 933-942.

Fujishige S. Submodular Functions and Optimization [M]. Elsevier, 2005.

Du D L, Lu R X, Xu D C. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmica, 2012, 63: 191-200.

Li Y, Du D L, Xiu N H, et al. A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties [J]. Theoretical Computer Science, 2013, 476: 109-117.

Ravi R, Sinha A. Approximation algorithms for multicommodity facility location problems [J]. SIAM Journal on Discrete Mathematics, 2010, 24: 538-551.

Mahdian M. Facility location and the analysis of algorithms through factor-revealing programs [D]. Massachusetts Institute of Technology, 2004.

Li G D, Wang Z, Wu C C. Approximation algorithms for the stochastic priority facility location problem [J]. Optimization, 2013, 62(7): 919-928.

Wang F M, Xu D C, Wu C C. Approximation algorithms for the priority facility location problem with penalties [J]. Journal of Systems Science and Complexity, 2014, DOI: 10.1007/s11424-014-2157-2.

Fleischer L, Iwata S. A push-relabel framework for submodular function minimization and applications to parametric optimization [J]. Discrete Applied Mathematics, 2003, 131: 311-322.

[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 Shuo, ZHU Zhibin, ZHANG Benxin. A simple primal-dual algorithm for minimization of the sum of three convex functions [J]. Operations Research Transactions, 2018, 22(2): 127-138.
[7]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[8]	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.
[9]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[10]	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.
[11]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[12]	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.
[13]	ZHANG Huizhen, WEI Xin, MA Liang. A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem [J]. Operations Research Transactions, 2015, 19(4): 37-47.
[14]	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.
[15]	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.

Approximation algorithms for the priority facility location problem with submodular penalties

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments