摘要
研究带惩罚和软容量约束的下界设施选址问题.扩展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-α)ρ的双标准近似算法.
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＋a/1-ap as that for the problem without penalties in Hierarchical placement and network design problems （Guha S, Meyerson A, Munagala K. HierarchicM placement and network design problems [C]/ / Proceedings of Foundations of Computer Science, 2000： 892328, DOI： 10.1109/SFC- S.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.
出处
《运筹学学报》
CSCD
北大核心
2013年第1期117-126,共10页
Operations Research Transactions
基金
supported by National Natural Science Foundation of China(Nos.11201013,11071268)
关键词
下界约束设施选址
近似算法
双标准算法
lower-bounded facility location, approximation algorithm, bicriteria algorithm.
