标题:基于设施选址问题的费用分配问题的近似算法
作者:王继强;李国君
作者机构:[王继强] 山东大学数学与系统科学学院, 济南, 山东 250100, 中国.;[李国君] 山东大学数学与系统科学学院, 济南, 山东 250100, 中国 更多
来源:计算机工程与应用
出版年:2006
卷:42
期:13
页码:13-14+32
DOI:10.3321/j.issn:1002-8331.2006.13.004
关键词:设施选址; 费用分配; 近似算法; 原始与对偶规划
摘要:许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问 题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法给出了该问题的一个更好的近似算法。
收录类别:CSCD
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=JSGG200613003&DbName=CJFQ2006
TOP