Abstract
In the dissertation, we study approximation algorithms for several variants of the Steiner tree problem. The classical Steiner tree problem asks for a shortest acyclic network interconnecting a given subset of the vertices (terminals). Steiner trees are important in various applications such as multicast routing, evolutionary tree reconstruction in biology and VLSI routing. The first problem is the the Steiner consensus string problem. One of the applications of this problem is to reconstruct the evolutionary tree in biology. Given a finite set $W$ of $n$ strings (sequences) and an evolutionary tree structure T with a root vertex and n leaves, each of which is labeled with a unique string of W, the Steiner consensus string is a string which labels to the root that minimizes some distance functions. The median string problem is to find a Steiner consensus string that minimizes the sum of its Levenshtein distance to each string of the set W. We also study the centre string problem that finds a Steiner consensus string minimizing the maximum of Levenshtein distances to each string of the set W. In this dissertation, we shall show a (2-2/n)-approximation algorithm on median string problem and a 2-approximation algorithm on centre string problem. The second portion of this dissertation, we discuss the full Steiner tree problem and bottleneck full Steiner tree problem. The applications of both problems have the reconstruction of evolutionary tree, VLSI routing and telecommunications. Given a graph G=(V,E) with nonnegative edge lengths and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. The full Steiner tree problem (FSTP) is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem (BFSTP) is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. We shall present an approximation algorithm with performance ratio 2p for the FSTP, where p is the best-known performance ratio for the Steiner tree problem. Then, we give an exact algorithm of O(|E|log|E|) time to solve the BFSTP. Finally, motivated by the applications of multicasting and broadcasting, we investigate two k-source shortest paths Steiner (spanning) tree problems of graphs with k given sources, and a set of destinations. Let G=(V,E) be an undirected graph with nonnegative edge lengths, S a set of k specified sources and a set R of destinations. The sets S and R do not need to be disjoint. The first problem is the k-source maximum vertex shortest paths Steiner (spanning) tree (k-MVST) problem, in which we want to find a Steiner tree T which connects all sources and destinations such that the maximum total distance from any vertex in R to all sources is minimized. The other problem is the k-source maximum source shortest paths Steiner (spanning) tree (k-MSST) problem, in which the objective function is the maximum total distance from any source to all vertices in R. Both problems have been shown to be NP-complete even when k=2 and |R|=|V|. In this dissertation, we shall propose a polynomial time approximation scheme (PTAS) for the 2-MVST problem. For the 2-MSST problem, we first give a (2+e)-approximation algorithm for any e>0, and then present a PTAS for the case that the input graphs are restricted to metric graphs. Finally, we show that there are simple 3-approximation algorithms for both problems with arbitrary k.