A polynomial time approximation scheme for the problem of interconnecting highways
The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a (1+1/c)-approximation to the optimal cost in O(n(O)(c)log(n) time.
polynomial time approximation scheme interconnecting highways minimum steiner tree patching dynamic programming