給定一個圖G = (V,E)，其中邊的長度必須要是正實數，以及一個端點子集R包含於V，所謂的Steiner樹，就是指要在圖G上找到一個連通的，而且沒有環路的子圖(即生成樹)並且包含了所有在R中的端點。Steiner樹問題就是要從圖G中找出一棵總成本花費最少的Steiner樹。
類似Steiner樹，給定一個完全圖G = (V,E)，其中邊的長度必須要是正有理數，以及兩個端點的子集R包含於V和R'包含於R，一個部份終端點Steiner樹也是一個Steiner樹，它包含了所有在R中的端點，並且所有在R'中的端點，在此Steiner樹中都必須在葉點上。這篇論文的主要問題就是要從圖G中找出一棵總成本花費最少的部份終端點Steiner樹。先前對於這個問題的最好的演算法近似比率為2p，其中p為目前最好的Steiner樹之演算法的近似比率。在這篇論文裡面，我們將改進這個演算法的近似比率從2p到2p–p/(3p–2)–e ，其中 e 的範圍為0至p–(p/(3p–2))之間。

Given a graph G = (V,E) with a length (or cost) function c : E -> R+ on the edges, and a subset R is a subset of V of vertices, a Steiner tree is a connected and acyclic subgraph of G which contains all vertices in R. The Steiner tree problem is to find a Steiner tree of the minimum length in G.
Like the Steiner tree, given a complete graph G = (V,E) with a length (or cost) function c : E -> Q¸ on the edges, and two proper subsets R is a subset of V and R' is a subset of R, a
partial-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R' must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum length in G. The previously best-known approximation ratio of the problem is 2p, where p is the approximation ratio of the Steiner tree problem. In this thesis, we improve the ratio from 2p to 2p - p/(3p-2)-e , where e is some non-negative number between 0 and p-p/(3p-2).

[1] S. Arora, "Polynomial Time Approximation Schemes for Euclidean TSP and Other Geomet-
ric Problems," Proceedings 37th Annual Symposium on Foundations of Computer Science ,
2-11, 1996.
[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, "Proof verification and the
hardness of approximation problems," Journal of the Association for Computing Machinery,
vol. 45, pp. 501-555, 1998.
[3] P. Berman, M. Furer and A. Zelikovsky, "Applications of the Matroid Parity Problem to
Approximating Steiner Trees," Tech. Rep. 980021, Computer Science Dept., UCLA, Los
Angeles, 1998.
[4] M. Bern and P. Plassmann, "The Steiner problem with edge lengths 1 and 2," Information
Processing Letters, vol. 32(4), pp. 171-176, 1989.
[5] A. Caldewll, A. Kahng, S. Mantik, I. Markov, and A. Zelikovsky, "On wirelength estimations
for row-based placement," in Proceedings of the 1998 International Symposium on Physical
Design (ISPD), pp. 4-11.
[6] Y. H. Chen, C. L. Lu, and C. Y. Tang, "On the full and bottleneck full Steiner tree
problems," in Proceedings of the 9th Annual International Conference on Computing and
Combinatorics (COCOON), LNCS 2697, pp. 122-129, 2003.
[7] X. Cheng and D. Z. Du, Steiner Trees in Industry, Kluwer Academic Publishers, Dordrecht,
Netherlands, 2001.
[8] A. E. F. Clementi and L. Trevisan, "Improved Non-Approximability Results for Minimum
Vertex Cover with Density Constraints," Electronic Colloquium on Computational Complexity, TR96-016 ,1996.
[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms
(Second Edition), MIT Press, Cambridge, 2001.
[10] D. E. Drake and S. Hougardy, "On approximation algorithms for the terminal Steiner tree
problem," Information Processing Letters, 89(1), pp. 15-18, 2004.
[11] D. Z. Du, J. M. Smith, and J. H. Rubinstein, Advance in Steiner Tree, Kluwer Academic
Publishers, Dordrecht, Netherlands, 2000.
[12] L. Foulds and R. Graham, "The Steiner problem in phylogeny is NP-complete," Advances
in Applied Mathematics, vol. 3, pp. 43-49, 1982.
[13] L. Foulds and V. J. Rayward-Smith, "Steiner problems in graphs: Algorithms and applica-
tions," Eng. Optimization 7, pp. 7-16, 1983.
[14] B. Fuchs, "A note on the terminal Steiner tree problem," Information Processing Letters,
vol. 87, pp. 219-220, 2003.
[15] M. Garey, R. Graham, and D. Johnson, "The complexity of computing Steiner minimal
trees," SIAM Journal on Applied Mathematics, vol. 32, pp. 835-859, 1977.
[16] M. Garey and D. Johnson, "The rectilinear Steiner problem is NP-complete," SIAM Journal
on Applied Mathematics, vol. 32, pp. 826-834, 1977.
[17] D. Graur and W. H. Li, Fundamentals of Molecular Evolution (2nd Edition), Sinauer Pub-
lishers, Sunderland, Massachusetts, 2000.
[18] S. L. Hakimi, "Steiner's problem in graphs and its implications," Networks 1, pp. 113-133,
1971.
[19] M. Hanan, "On Steiner's problem with rectilinear distance," J. SIAM Appl. Math. 14, pp.
255-265, 1966.
[20] S. Y. Hsieh and H. M. Gao, "On the partial-terminal Steiner tree problem," Journal of
Supercomputing, vol. 41, no. 1, pp. 41-52, 2007.
[21] S. Hougardy, and H. J. PrÄomel, "A 1.598 approximation algorithm for the Steiner prob-
lem in graphs," in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete
Algorithms, SIAM, Philadelphia, ACM, New York, pp. 448-453, 1999.
[22] F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem, Annuals of Discrete
Mathematices 53, Elsevier Science Publishers, Amsterdam, 1992.
[23] F. K. Hwang and D. S. Richards, "Steiner tree problems," Networks 22, pp. 55-89, 1992.
[24] A. B. Kahng and G. Robins, On Optimal Interconnections for VLSI, Kluwer Publishers,
1995.
[25] R. Karp, "Reducibility among combinatorial problems," in R. E. Miller, J. W. Thatcher
eds.: Complexity of Computer Computations, Plenum Press, New York, pp. 85-103, 1972.
[26] M. Karpinski and A. Zelikovsky, "New Approximation Algorithms for the Steiner Tree
Problem," Journal of Combinatorial Optimization, 1 , pp. 47-65, 1997.
[27] B. Korte, H. J. PrÄomel and A. Steger, Steiner trees in VLSI-layout, in B. Korte, L. Lovasz, H.
J. PrÄomel and A. Schrijver (eds.) Paths, Flows, and VLSI-Layout, Springer-Verlag, Berlin,
pp. 185-214, 1990.
[28] H. W. Kuhn, "Steiner's problem revisited, in G. B. Dantzig and B. C. Eaves (eds.)," Studies
in Optimization, Studies in Math. 10 Math. Assoc. Amer., pp. 53-70, 1975.
[29] A. Y. Levin, "Algorithm for shortest connection of a group of graph vertices," Sov. Math.
Dokl. 12, pp. 1477-1481, 1971.
[30] G. H. Lin and G. L. Xue, "On the terminal Steiner tree problem," Information Processing
Letters, vol. 84(2), pp. 103-107, 2002.
[31] C. L. Lu, C. Y. Tang, R. C. T. Lee, "The full Steiner tree problem in phylogeny," Theoretical
Computer Science, vol. 306(1-3), pp. 55-67, 2004.
[32] N. Maculan, "The Steiner problem in graphs," Ann. Discrete Math. 31, pp. 185-212, 1987.
[33] F. V. Martinez, J. C. d. Pina, and J. Soares, "Algorithms for terminal Steiner trees," in
Proceedings of the 11th Annual International Conference on Computing and Combinatorics
(COCOON), LNCS 3595, pp. 369-379, 2005.
[34] C. H. Papadimitriou and M. Yannakakis, "Optimization, approximation, and complexity
classes," in Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 229-234,
1988.
[35] H. J. PrÄommel and A. Steger, "RNC-Approximation Algorithms for the Steiner Problem,"
Proceedings 14th Annual Symposium on Theoretical Aspects of Computer Science, pp. 559-
570, 1997.
[36] G. Robins and A. Zelikovsky, "Improved Steiner tree approximation in graphs," in Pro-
ceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.
770-779, 2000.
[37] H. Takahashi and A. Matsuyama, "An Approximate Solution for the Steiner Problem in
Graphs," Math. Jap. 24, pp. 573-577, 1980.
[38] S. Voss, "Steiner-Probleme in Graphen," Mathematical Systems in Economics 120, Anton
Hein, Frankfurt-am-Main, 1990.
[39] D. B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, Upper Saddle
River, 2001.
[40] P. Winter, "Steiner Problem in Networks: A survey," Networks 17, pp. 129-167, 1987.
[41] M. Zacharis, EncyklopÄadie der Mathematischen Wissenschaften, III AB9.
[42] A. Zelikovsky, "An 11=6-Approximation Algorithm for the Network Steiner Problem," Al-
gorithmica 9, pp. 463-470, 1993.
[43] A. Zelikovsky, "Better Approximation Bounds for the Network and Euclidean Steiner Tree
Problems," Technical report CS-96-06, University of Virginia, 1996.