Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

摘要

In this paper, 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 we use costs cs units. The goal is to minimize the total length of the tree plus the penalties. We prove that the problem admits a polynomial time approximation scheme, if the points lie in the plane. Our PTAS uses a new technique which allows us to bypass major requirements of Arora's framework for approximation schemes for geometric optimization problems. It may thus open new possibilities to find approximation schemes for geometric optimization problems that have a complicated topology. Furthermore the techniques we use provide a more general framework which can be applied to geometric optimization problems with more complex objective functions.