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 approximatio...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.展开更多
基金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.