A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways |
| |
Authors: | Xiuzhen Cheng Joon-Mo Kim Bing Lu |
| |
Affiliation: | (1) Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA |
| |
Abstract: | 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 -approximation to the optimal cost in O(nO(c)log(n) time. |
| |
Keywords: | interconnecting highways polynomial time approximation scheme minimum Steiner tree patching dynamic programming |
本文献已被 SpringerLink 等数据库收录! |