Fault-tolerant Concave Facility Location Problem with Uniform Requirements

Fault-tolerant Concave Facility Location Problem with Uniform Requirements

导出

摘要 In this paper, we consider the fault-tolerant concave facility location problem （FTCFL） with uniform requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation factor is proved to be 1.52. In this paper, we consider the fault-tolerant concave facility location problem （FTCFL） with uniform requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation factor is proved to be 1.52.

作者 Xing WANG Da-Chuan XU Zheng-Hai HUANG

机构地区 Department of Mathematics Department of Applied Mathematics

出处《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2012年第3期475-484,共10页 应用数学学报（英文版）

基金 Supported by the National Natural Science Foundation of China (No. 60773185, 11071268, 10871144) Beijing Natural Science Foundation (No. 1102001)

关键词 approximation algorithm facility location problem dual-fitting approximation algorithm, facility location problem, dual-fitting

分类号 TP302.8 [自动化与计算机技术—计算机系统结构] O223 [理学—运筹学与控制论]

引文网络
相关文献

参考文献20

1Ageev, A., Ye, Y., Zhang, J. Improved combinatorial apporximation algorithms for the k-level facility location problem. SIAM Journal on Discrete Mathematics, 18:207-217 (2004).
2Byrka, J., Aardal, K.I. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing, 39:2212-2213 (2010).
3Byrka, J., Srinivasan, A., Swamy, C. Fault-tolerant facility location: a randomized dependent LP-rounding algorithm. In: Proceedings of IPCO, 2010, 244-257.
4Charikar, M., Guha, S. Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing, 34:803-824 (2005).
5Chen, X., Chen, B. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica, 53:263-297 (2009).
6Guha, S., Khuller, S. Greedy strike back: improved facility location algorithms. Journal of Algorithms, 31:228-248 (1999).
7Guha, S., Meyerson, A., Munagala, K. A constant factor approximation algorithm for the fault-tolerant facility location problem. Journal of Algorithms, 48:429-440 (2003).
8Hajiaghayi, M.T., Mahdian, M., Mirrokni, V.S. The facility location problem with general cost functions. Networks, 42:42-47 (2003).
9Jain, K., Mahdian, MI, Markakis, E., Saberi, A., Vazirani, V.V. Greedy facility location algorithm analyzed using dual fitting with factor-revealing LP. Jounal of the ACM, 50:795-824 (2003).
10Jain, K., Vazirani, V.V. An approximation algorithm for the fault tolerant metric facility location problem. Algorithmica, 38:433-439 (2003).

1WU 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.
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.
3WANG 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
4Min LIU,Hong-mei LIU.Vertex-Fault-Tolerant Cycles Embedding on Enhanced Hypercube Networks[J].Acta Mathematicae Applicatae Sinica,2016,32(1):187-198.
5Fu Rong,Shen Hong.AN ALGORITHM FOR DETERMINING CONCAVE VERTEX OF OBJECT BASED ON VECTOR PRODUCT[J].Journal of Electronics(China),2010,27(2):212-217.
6Chun-yan JIANG,Gai-di LI,Zhen WANG.An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties[J].Acta Mathematicae Applicatae Sinica,2014,30(1):187-192.
7匡奕军,诸克军.Capacitated Dynamic Facility Location Problem Based on Tabu Search Algorithm[J].Journal of Donghua University(English Edition),2007,24(5):677-681.
8季赛,王芳,刘文杰,袁晓敏.Twice-Hadamard-CNOT attack on Li et al.＇s fault-tolerant quantum private comparison and the improved scheme[J].Frontiers of physics,2015,10(2):73-78. 被引量：2
9Lei Ma Hongmei Liu.Edge-Fault-Tolerant Properties of Augmented Cubes[J].Journal of Systems Science and Information,2009,7(4):333-341.
10YANG Dong-Hui,Guo Bao-Zhu.ON NODAL LINE OF THE SECOND EIGENFUNCTION OF THE LAPLACIAN OVER CONCAVE DOMAINS IN R^2[J].Journal of Systems Science & Complexity,2013,26(3):483-488.

Acta Mathematicae Applicatae Sinica

2012年第3期

浏览历史

内容加载中请稍等...

Fault-tolerant Concave Facility Location Problem with Uniform Requirements

参考文献20

相关作者

相关机构

相关主题

浏览历史