Fault-tolerant Concave Facility Location Problem with Uniform Requirements  

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

机构地区：[1]Department of Mathematics,School of Science,Tianjin University,Tianjin 300072,China [2]Department of Applied Mathematics,Beijing University of Technology,Beijing 100124,China

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

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

摘　　要：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.

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

分 类 号：TP302.8[自动化与计算机技术—计算机系统结构] O223[自动化与计算机技术—计算机科学与技术]