內部史坦納森林之近似演算

Abstract

給定一個完全圖G跟一些不相交的點集R={R1,R2,...,Rk}，內部史坦納森林的問題就是找一個總重量最輕的史坦納森林，而且在這史坦納森林裡每個點集內的點都要求相互連接且每個R點都不是葉子。若ρ'是史坦納森林問題的一個近似解,m是史坦納森林的連接組件（connected component）的數量，則我們針對內部史坦納森林的問題給予一個2ρ'+4logm的近似解。若k=1，這問題就是內部史坦納樹的問題。ρ是史坦納樹問題的近似解而且之前最好的結果是2ρ+1，我們則給予一個新的近似解2ρ。 此外，如果我們允許最後的圖可能會有循環（cycle）在裡面，也就是不再要求是樹或森林，我們就稱呼這問題是內部史坦納子圖的問題，而且同樣地也給予一個近似解的答案。

Given a complete graph G = (V,E) with metric weight function c : E → R+ and a list R = {R1,R2, ...,Rk} of disjoint vertex subset of V , an internal Steiner forest problem is seek a Steiner forest such that the vertices in Ri are connected with each other and restricted to be internal vertex for this forest. Suppose ρ′ is the approximation ratio for the Steiner forest problem, and m is the number of connected component. we give a approximation ratio 2ρ′ + 4 logm for this problem. If k = 1, this problem is an internal Steiner tree problem, due to Hsieh. Suppose ρ is the approximation ratio for the Steiner tree problem, the previous result of an internal Steiner tree problem is 2ρ + 1 and we also obtain an approximation ratio 2ρ. Moreover, if our result graph allow to have cycle in the above problem, we address this case as internal Steiner subgraph problem and also give an approximation ratio.