摘要
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.
基金
Supported by the National Natural Science Foundation of China (No. 60773185, 11071268, 10871144)
Beijing Natural Science Foundation (No. 1102001)
