快速有向性的Steiner Tree近似演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：67

、訪客IP：18.227.102.127

姓名

謝明益(Ming-I Hsieh) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

快速有向性的Steiner Tree近似演算法
(A Faster Approximation Algorithm for Directed Steiner Tree Problem)

相關論文

★ 具多重樹狀結構之可靠性群播傳輸	★ 在嵌入式行動裝置上設計與開發跨平台Widget
★ 在 ARM 架構之嵌入式系統上實作輕量化的手持多媒體播放裝置圖形使用者介面函式庫	★ 基於網路行動裝置所設計可擴展的服務品質感知GStreamer模組
★ 針對行動網路裝置開發可擴展且跨平台之GSM/HSDPA引擎	★ 於單晶片多媒體裝置進行有效率之多格式解碼管理
★ IMS客戶端設計與即時通訊模組研發：個人資訊交換模組與即時訊息模組實作	★ 在可攜式多媒體裝置上實作人性化的嵌入式小螢幕網頁瀏覽器
★ 以IMS為基礎之及時語音影像通話引擎的實作:使用開放原始碼程式庫	★ 電子書嵌入式開發: 客制化下載服務實作, 資料儲存管理設計
★ 於數位機上盒實現有效率訊框參照處理與多媒體詮釋資料感知的播放器設計	★ 具數位安全性的電子書開發：有效率的更新模組與資料庫實作
★ 適用於異質無線寬頻系統的新世代IMS客戶端軟體研發	★ 在可攜式數位機上盒上設計並實作重配置的圖形使用者介面
★ Friendly GUI design and possibility support for E-book Reader based Android client	★ Effective GUI Design and Memory Usage Management for Android-based Services

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

中文摘要:
在本論文中，我們提出一個新的有向性的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.

關鍵字(中)

★ 群撥演算法

關鍵字(英)

★ Multicast Routing
★ Steiner Tree

論文目次

Table of Contents
Abstract ii
Table of Contents iii
1 Introduction 1
2 Related Works 7
2.1 Compress Graph and Properties of Directed Steiner
Tree Algorithm . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Introduction to Zelikovsky’s l-restricted tree . . . . . . 11
2.3 Charikar et al’s DSP Algorithm and Proof . . . . . . . 12
2.3.1 Charikar et al’s DSP Algorithm . . . . . . . . . 12
2.3.2 Charikar et al’s proof for approximation ratio . 14
2.4 Introduction to Roos’ DSP Algorithm . . . . . . . . . . 15
3 Directed Steiner Tree Problem 16
3.1 Preprocess and Merge Operator . . . . . . . . . . . . . 16
3.2 Greedy algorithm for k-shortest path tree . . . . . . . . 19
3.3 To choose the better density (l − 1)-level tree . . . . . 20
3.4 To construct a set of l-level tree with 1, 2, ..., k terminals
by the better density l − 1-level tree . . . . . . . . . . . 22
3.5 To construct a l-level tree with k terminals . . . . . . . 24
3.6 Analysis for Time Complexity and Space Complexity . 25
4 Implementation and Test Results 27
5 Approximation Ratio 36
5.1 Approximation Ratio Functions . . . . . . . . . . . . . 36
5.2 Greedy algorithm’s approximation ration function and
Ideal approximation ratio function . . . . . . . . . . . . 38
5.3 Charikar et al’s approximation ratio function . . . . . . 39
5.4 Modified Charikar et al’s approximation ratio function 40
5.5 Charikar et al’s approximation ratio function with
Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . 41
5.6 The Density Functions . . . . . . . . . . . . . . . . . . 43
5.7 The approximation ratio function of our approximation
algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.8 Comparison between those approximation ratio functions 52
6 Conclusions 54

參考文獻

[1] F. K. Hwang, D. S. Richards, and P. Winter, “The steiner tree
problem,” North-Holland and 1992.
[2] M. Garey and D. Johnson, “Computers and intractability: A
guide to the theory of np-completeness,” Freeman and San Francisco
(1978).
[3] M. Bern and P. Plassman, “The steiner problems with edge
lengths 1 and 2,” Information Processing Letters and 32:171-176
(1989).
[4] M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha,
and M. Li, “Approximation algorithms for directed steiner problems,”
vol. 33, pp. 73–01, 1999.
[5] L. Kou, G. Markowsky, and L. Berman, “A fast algorithm for
steiner trees,” Acta Informatica and 15 and pp. 141-145 (1981).
[6] P. Berman and V. Ramaiyer, “Improved approximation algorithms
for the steiner tree problem,” in Journal of Algorithms
and 17:381-408 (1994).
[7] H. Takahashi and A. Matsuyama, “An approximate solution for
the steiner problem in graphs,” Math. Japonica and Vol. 24 and
pp.573-577 (1980).
[8] M. Karpinsky and A. Zelikovsky, “New approximation algorithms
for the steiner tree problem,” tech. rep. Technical Report and
Electronic Colloquium on Computational Complexity (ECCC):
TR95-030 (1995).
[9] S. Ramanathan, “Multicast tree generation in networks with
asymmetric links,” IEEE Infocom’96 and IEEE/ACM Transactions
on Networking and Vol.4 and pp.558-568 (1996).
[10] H. Salama, “Evaluation of multicast routing algorithms for realtime
communication on high-speed networks,” IFIP Sixth Internation
Conference on High Performance Networking and pp.27-42
(1995).
[11] P. Winter, “Steiner problem in networks: A survey,” Networks
and 17:129-167 (1987).
[12] A. Zelikovsky, “A series of approximation algorithms for the
acyclic directed steiner tree problem,” vol. 18, pp. 99–110, 1997.
[13] S. Roos, “Scheduling for remove and other partially connected
architectures,” Internal Report. (2001).
[14] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, “Introduction
to algorithms,” 26.3.

指導教授

吳曉光(Eric Hsiao-Kuang Wu)

審核日期

2003-7-16

推文