Euclidean Prize-collecting Steiner Forest
Preprint
Abstract
In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k-Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et al. [12] for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case).Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Product Multicommodity Flow in Wireless NetworksIEEE Transactions on Information Theory, 2008
- Tighter Bounds for Graph Steiner Tree ApproximationSIAM Journal on Discrete Mathematics, 2005
- Sparsest cuts and concurrent flows in product graphsDiscrete Applied Mathematics, 2004
- Embedding Tree Metrics into Low-Dimensional Euclidean SpacesDiscrete & Computational Geometry, 2000
- A Constant-Factor Approximation Algorithm for thek-MST ProblemJournal of Computer and System Sciences, 1999
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related ProblemsSIAM Journal on Computing, 1999
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- A note on the prize collecting traveling salesman problemMathematical Programming, 1993
- The prize collecting traveling salesman problemNetworks, 1989
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989