基于设施选址的Steiner问题的算法

被引：4

作者：

王继强

李国君

机构：

[1] 山东大学数学与系统科学学院

来源：

计算机科学 | 2007年 / 09期

关键词：

Steiner树-星; 设施选址; 近似算法; 问题转化;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

在设施选址问题的基础上给出了广义Steiner树-星问题的两个近似比分别为3.55和3.582的近似算法,并在问题转化的基础上研究了其他若干特殊情形的Steiner树问题的近似算法。

引用

收藏

页码：181 / 182

页数：2

相关论文

共 2 条

[1] The Complexity of Computing Steiner Minimal Trees[J] . M. R. Garey,R. L. Graham,D. S. Johnson.SIAM Journal on Applied Mathematics . 1977 (4)
[2] An 1.582-approximation algorithm for the metric uncapacitated facility location problem .2 Sviridenko M. Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimiza- tion . 2002