带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究

研究带惩罚和软容量约束的下界设施选址问题. 扩展Guha等(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)和Karger等(Karger D R,Minkoff M. Building steiner trees with incomplete global knowledge C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329)的工作到带有惩罚的下界约束设施选址问题，提出了一个新的双标准近似算法，得到了同样的近似比ρ(1+α)/(1-α). 进一步考虑带惩罚和软容量约束的下界设施选址问题，得到了近似比为2ρ(1+α)/(1-α)的双标准近似算法.

Bicriteria approximation algorithms for the lower-bounded facility location problem with penalties and soft-capacity

We study the lower-bounded facility location problem with penalties (LBFLP) and the soft-capacity LBFLP. For the LBFLP, we present an updated bicriteria approximation algorithm which maintains the same performance factor ρ(1+α)/(1-α) as that for the problem without penalties in Hierarchical placement and network design problems(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)and Building steiner trees with incomplete global knowledge(Karger D R, Minkoff M. Building steiner trees with incomplete global knowledge C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329). We further extend this result to the soft-capacitated LBFLP and achieve a performance factor twice as much as that for LBFLP.