An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties

An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties

导出

摘要 In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP. In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.

作者 Chun-yan JIANG Gai-di LI Zhen WANG

机构地区 Basic Courses Teaching Department Department of Applied Mathematics

出处《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2014年第1期187-192,共6页 应用数学学报（英文版）

基金 Supported in part by Hebei Province Department of Education Fund under Grant No.Z2012017 the National Natural Science Foundation of China under Grant No.11371001 and 11201013

关键词 dynamic facility location problem approximation algorithm submodular function dynamic facility location problem approximation algorithm submodular function

分类号 O224 [理学—运筹学与控制论]

引文网络
相关文献

参考文献2

1姜春艳,徐大川.带惩罚的动态设施选址问题的近似算法[J].应用数学学报,2009,32(6):988-996. 被引量：4
2XU DaChuan Department of Applied Mathematics,Beijing University of Technology,Beijing 100124,China.A cross-monotonic cost sharing method for the facility location game with service installation costs[J].Science China Mathematics,2009,52(11):2530-2536. 被引量：4

二级参考文献28

1XU DaChuan Department of Applied Mathematics,Beijing University of Technology,Beijing 100124,China.A cross-monotonic cost sharing method for the facility location game with service installation costs[J].Science China Mathematics,2009,52(11):2530-2536. 被引量：4
2Jiawei Zhang.Approximating the two-level facility location problem via a quasi-greedy approach[J]. Mathematical Programming . 2006 (1)
3Hervé Moulin,Scott Shenker.Strategyproof sharing of submodular costs:budget balance versus efficiency[J]. Economic Theory . 2001 (3)
4Byrka J,Aardal K.An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing . 2009
5Li Y,Xu D.Soft-capacitated facility location game. Acta Math Appl Sin Engl Ser .
6Devanur N R,Mihail M,Vazirani V V.Strategyproof cost-sharing mechanisms for set cover and facility location games. Decis Supp Syst . 2005
7Shmoys D,Tardos E,Aardal K.Approximation algorithms for facility location problems (extended ab- stract). Proceedings of the 29th ACM Symposium on Theory of Computing (STOC) . 1997
8Guha S,Khuller S.Greedy strike back: Improved facility location algorithms. Journal of Algorithms . 1999
9Jain K,Mahdian M,Saberi A.A new greedy approach for facility location problems. Proceedings of the 34th ACM Symposium on Theory of Computing (STOC) . 2002
10Du D,Wang X,Xu D.An approximation algorithm for the k-level capacitated facility location problem. J Comb Optim .

共引文献6

1姜春艳,徐大川.带惩罚的动态设施选址问题的近似算法[J].应用数学学报,2009,32(6):988-996. 被引量：4
2姜春艳,李改弟.软容量约束的动态设施选址问题的近似算法[J].系统科学与数学,2012,32(4):476-484.
3姜燕君,徐大川,张冬梅.平方度量动态设施选址问题的近似算法[J].运筹学学报,2018,22(3):49-58. 被引量：1
4吴晨晨,王丽,徐春明,徐大川.鲁棒动态设施选址问题的近似算法[J].运筹与管理,2020,29(5):61-66. 被引量：2
5苟海雯,宁爱兵,胡沁,张惠珍.带惩罚的无容量设施选址问题的降阶回溯算法[J].计算机工程与应用,2020,56(24):43-49.
6徐大川,杜东雷,吴晨晨.设施选址问题的近似算法综述[J].数学进展,2014,43(6):801-816. 被引量：4

1WANG Fengmin,XU Dachuan,WU Chenchen.Approximation Algorithms for the Priority Facility Location Problem with Penalties[J].Journal of Systems Engineering and Electronics,2015,26(5):1102-1114. 被引量：1
2ZHANG Liping(Institute of Applied Mathematics, Academia Sinica, Beijing 100080, China)WANG Changyu(Institute of Operations Research, Qufu Normal University, Qufu 273165, China).AN ALGORITHM FOR CONTINUOUS TYPE OPTIMAL SPHERICAL FACILITY LOCATION PROBLEM[J].Systems Science and Mathematical Sciences,1999,12(3):210-215.
3YUAN De-hui,FENG Yan,SHEN Yan-feng,YANG Shou-zhi.Primal-dual-pseudo Spline and Its Properties[J].Chinese Quarterly Journal of Mathematics,2013,28(3):376-382. 被引量：1
4Xing WANG,Da-Chuan XU,Zheng-Hai HUANG.Fault-tolerant Concave Facility Location Problem with Uniform Requirements[J].Acta Mathematicae Applicatae Sinica,2012,28(3):475-484.
5WANG Guanjun,CHEN Hanfu (Institute of Systems Science, Academia of Sinica, Beijing 100080, China).BEHAVIOR OF STOCHASTIC APPROXIMATIONALGORITHM IN ROOT SET OF REGRESSIONFUNCTION[J].Systems Science and Mathematical Sciences,1999,12(1):92-96.
6WU Chen Chen,DU Dong Lei,XU Da Chuan.An improved per-scenario bound for the two-stage stochastic facility location problem[J].Science China Mathematics,2015,58(1):213-220.
7Chang-feng Ma,Guo-ping Liang,Shao-peng Liu.A NEW SMOOTHING APPROXIMATION METHOD FOR SOLVING BOX CONSTRAINED VARIATIONAL INEQUALITIES[J].Journal of Computational Mathematics,2002,20(5):533-542.
8LU KeZhong1,2, CHEN GuoLiang1,2, FENG YuHong1,2, LIU Gang1,2 & MAO Rui1,2 1College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China,2National High Performance Computing Center at Shenzhen, Shenzhen 518060, China.Approximation algorithm for minimizing relay node placement in wireless sensor networks[J].Science China(Information Sciences),2010,53(11):2332-2342. 被引量：1
9唐艳.A fractal approximation algorithm for inverse initial-value problems of nonlinear differential equations[J].Journal of Chongqing University,2003,2(2):86-90. 被引量：1
10Curtis Craig,Randy W.Overbeek,Miles V.Condon,Shannon B.Rinaldo.美国国家橄榄球联盟(NFL)判罚中温度与攻击性行为的关系(英文)[J].Journal of Sport and Health Science,2016,5(2):205-210. 被引量：1

Acta Mathematicae Applicatae Sinica

2014年第1期

浏览历史

内容加载中请稍等...

An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties

参考文献2

二级参考文献28

共引文献6

相关作者

相关机构

相关主题

浏览历史