Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems
复制标题
DOI：
10.1007/s00453-007-9114-6
复制
发表时间：
2005-08
期刊：
影响因子：
1.1
通讯作者：
J. Remy;A. Steger
中科院分区：
文献类型：
--
作者：
J. Remy;A. Steger
在本文中，我们介绍了一种几何优化问题近似方案的新技术。作为示例问题，我们考虑几何斯坦纳树问题的以下变体。未包含在树中的每个点 u 都会受到 π(u) 个单位的惩罚。此外，我们使用的每个 Steiner 点都是 costcSunits。目标是最小化树的总长度加上惩罚。如果点位于平面上，我们的技术会产生该问题的多项式时间近似方案。
In this paper we introduce a new technique for approximation schemes for geometrical optimization problems. As an example problem, we consider the following variant of the geometric Steiner tree problem. Every pointuwhich is not included in the tree costs a penalty ofπ(u) units. Furthermore, every Steiner point that we use costscSunits. The goal is to minimize the total length of the tree plus the penalties. Our technique yields a polynomial time approximation scheme for the problem, if the points lie in the plane.