Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

摘要

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 point u which is not included in the tree costs a penalty of π(u) units. Furthermore, every Steiner point that we use costs c _S units. 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.