On several geometric network design problems
Jinhui Xu, Yang Yang · 2007
Geometric network design problems arise in many applications such as VLSI circuit design, telecommunications, road network design, medical imaging and site layout. Frequently encountered such problems include Traveling Salesman problem, spanner, geometric spanning tree, and some covering problems. Generally speaking, a geometric network design problem is to determine a minimum subgraph (in terms of the size or some other measure) of some underlying graphs which maintains certain properties. In this dissertation, we study the generalizations of several classical geometric network design problems. Our problems either consider more complicated geometric objects or use more general measures, and thus provide a better modeling for many real world problems. The first problem we study is a variant of the Traveling Salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n e-separated segments in two dimensional space. In this problem, the distance between two segment is not metric due to the shape of the segments. We present a polynomial time approximation scheme (PTAS) for the segment TSP problem. Our results are based on an interesting combinatorial result which bounds the total number of entry points in an optimal TSP tour and a generalization of Arora's technique for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O( n2(logn)O (1/e2)) time to compute a (1 + e)-approximation with probability ≥ 1/2, and can be derandomized with an additional factor of O( n2). The second problem we study is the Geometric Spanners of Segments, which can be viewed as a generalization of the classic geometric spanner. In this problem we are given a set of S of disjoint 2-D segments, find a spanning network G with size so that for any pair of points in S, there exists a path in G with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, and interval cover), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set of Steiner points in S and then construct a point spanner for the set of Steiner points. Our algorithm runs in O(| Q|+n2 logn) time, where Q is the set of Steiner points. We show that Q is an O(1)-approximation in terms of its size when S is relatively well separated by a constant. The third problem we study is an interesting generalization of the weighted vertex cover problem, called the Facility Terminal Cover (FTC) problem. In the FTC problem, each vertex is associated with a positive weight, each edge is associated with a positive demand, and the objective is to determine a subset of vertices and a capacity for each selected vertex so that the demand of each edge is covered by the capacity of one of its two endpoints and the total weighted capacity of all selected vertices is minimized. We present two linear time approximation algorithms for this problem: The first algorithm deterministically achieves an approximation ratio of 8 by using an interesting rounding technique and a lower-bounding technique; the second algorithm further improves the approximation ratio to 2e with some randomization techniques, where e is the natural logarithmic base. The second algorithm can be easily derandomized in quadratic time. The fourth problem we study is a natural generalization of the classical spanning tree problem called Minimum Spanning Tree with Neighborhoods (MSTN), which seeks a tree of length to span a set of 2D regions called neighborhoods. Each neighborhood contributes exact one node to the tree, and the MSTN has the total length among all possible trees spanning the set of nodes. When the regions considered are a set of disjoint 2D unit discs, we present the following approximation results: (1) A simple algorithm that achieves an approximation ratio of 7.4; (2) Lower bounds and two 3-approximation algorithms; (3) A PTAS for this problem. Our algorithms can be easily generalized to higher dimensions.