Euclidean Prize-collecting Steiner Forest

Details Euclidean Prize-collecting Steiner Forest Euclidean Prize-collecting Steiner Forest

2009-12-06

arxiv.org/abs/0912.1137v1

Computer Science

Data Structures and Algorithms

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Euclidean Prize-collecting Steiner Forest does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Euclidean Prize-collecting Steiner Forest, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Euclidean Prize-collecting Steiner Forest will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-242488