中文摘要: 在本論文中，我們提出一個新的有向性的Steiner Tree 近似演算法．Steiner Tree 的問題在於：給一個有向性的圖G=(V,E,c)這裡的c: E->R+ 是一個將邊轉換為值的函式，一個點的子集合（也就是terminals），及一個根vr ，有向性的Steiner Tree 問題在於如何尋找一個spanning tree 以根為起使點並連結到所有的terminals，並且使得spanning tree 上邊值的合為最小．DSP（Directed Steiner Tree Problem）常在一對多（Multicast）的資料傳送網路中被提起來改進其傳送時的成本．在本篇文章之前，Charikar 等人的DSP 演算法是在IDMR 方面最有名的．這個演算法能在O(n^lk^{2l-2}log n+m) 的時間內取得l(l-1)k^{1/l}的近似值的解（這裡的l 可是是任何大於1的值，n 是點的數量， 是邊的數量）．不過這個演算法需要很大量的計算效能．而這份論文提供一個更快的近似演算法，能在O(P^n_lP^k_l+n^2k+nm)的時間內求得相同等級或更好的近似解． Abstract Given a weighted directed graph G = (V,E,c), where c : E -> R+ isan edge length function, a subset X of vertices (terminals), and a root vertex vr, directed Steiner tree problem (DSP) asks for a minimum cost tree which spans paths from root vertex vr to each terminal. DSP is often raised in one-to-many (Multicast) data delivering network to improve the cost of the distribution tree1. Before this article, Charikar et al’s DSP algorithm is well known for IDMR. It achieves an approximation ratio of 1(l−1)k^(1/l) in O(n^lk^{2l-2)logn+m) times for any fixed level l > 1, where l is the level of the tree produced by the algorithm, n is the number of vertices, |V |, and k is the number of terminals, |X|. Charikar et al’s DSP algorithm is useful to improve for IDMR. However it requires a great amount of computing power. This thesis provides a faster approximation algorithm based on ideas of Charikar et al’s DSP algorithm with better time complexity, O(P^n_lP^k_l+n^2k+nm), and a better approximation ratio for any level l > 1.
