研究带惩罚和软容量约束的下界设施选址问题.扩展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....研究带惩罚和软容量约束的下界设施选址问题.扩展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-α)ρ的双标准近似算法.展开更多
基金supported by National Natural Science Foundation of China(Nos.11201013,11071268)
文摘研究带惩罚和软容量约束的下界设施选址问题.扩展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-α)ρ的双标准近似算法.
