- 學位論文
現存Steiner Problem之近似演算法的部分改進
Some Improvements of Existing Approximation Algorithms for the Steiner Problem in Graphs
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
並列摘要
Steiner tree 的概念可廣泛應用在網路、通訊、以及 VLSI 的設 計等方面。由於其重要性，從80年代開始遂有相當多的論文 探討該項 問題。本論文的研究目的主要在將數個著名的近似演算法 作一整理介 紹，並重新加以證明，改善了部分的近似率（Approxi- mation Ratio） ，同時提出對各近似解作一後置處理，在不增加整 體時間複雜度的情況 下得到更好的結果。 The concept of Steiner tree is widely applied to the design of networks, communications, and VLSI, etc. Due to its importance, there are a lot of papers studying the Steiner tree problem since 1980. The purpose of this thesis is to introduce several famous approximation algorithms, illustrate how they work, and reprove some of them to improve approximation ratios. Finally, a post process for all approximate solutions is proposed such that a better solution may be obtained under the condition of not increasing the time-complexity.
延伸閱讀
- 黃立沅（2015）。節點分歧受限下的有向圖中尋找有向Steiner Tree的近似演算法〔碩士論文，國立清華大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0016-0312201510303064
- Hsu, W. Y. (2013). 離散型 STURM-LIOUVILLE 算子的固有值問題之研究 [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-2211201316401416
- Chen, W. C., & Chen, J. L. (2018). 簡化的解決創新問題演算法：S-ARIZ. 中國機械工程學刊, 39(1), 21-32. https://www.airitilibrary.com/Article/Detail?DocID=02579731-201802-201804250013-201804250013-21-32
- Chan, C. Y. (2009). 文件特徵化問題的改進演算法 [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2009.00661
- Tian, M., & Gong, J. Y. (2014). Strong Convergence of Modified Algorithms Based on the Regularization for the Constrained Convex Minimization Problem. Abstract and Applied Analysis, 2014(), 928-936-1489. https://doi.org/10.1155/2014/870102