Journal
ALGORITHMICA
Volume 55, Issue 1, Pages 240-267Publisher
SPRINGER
DOI: 10.1007/s00453-007-9114-6
Keywords
Computational geometry; Steiner tree problem; Approximation schemes
Ask authors/readers for more resources
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 pi(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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available