This project's goal is the study of approximations for Steiner minimum trees (SMTs) and related problems. This study extends the PI's research, supported under CCR-92- 08913, on the analysis and the designs of polynomial-time approximations for SMTs. The project includes finding new techniques to solve or make significant progress in both the analysis and construction/implementation of the following problems in the area of SMTs: (1) Open problems on the Steiner ratio (such as, Chung-Gilbert's conjecture, Graham- Hwang's conjecture, and Smith's sausage conjecture); (2) Determination of the performance ratios for various approximations (such as, Chang's approximations, Smith-Lee- Liebman's approximation, and Kahng-Robin's approximation); (3) New approximation algorithms using the variable metric method; (4) Investigation of a conjecture about SMTs approximations and hardness of finding approximate SMTs; (5) Establishment of significant lower bounds for the performance ratio of polynomial-time approximations; (6) Improvement of the analysis of approximations of Zelikovsk's; and (7) Construction of good approximation algorithms for related problems.***
