Approximation of Steiner Minimum Trees and Applications

点击翻译按钮获取中文摘要

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.***