Approximation of Steiner Minimum Trees and Applications

这个项目的目标是研究Steiner最小树（SMT）的近似和相关问题。 本研究扩展了PI在CCR-92- 08913支持下的研究，即SMT多项式时间近似的分析和设计。 该项目包括寻找新的技术来解决或在分析和构建/实施SMT领域的以下问题方面取得重大进展：（如Chung-Gilbert猜想、Graham- Hwang猜想和Smith香肠猜想）;（2）确定各种近似的性能比（3）用变尺度方法的新的近似算法;（4）关于SMT近似的一个猜想的研究和寻找近似SMT的困难;（5）建立多项式时间近似的性能比的显著下界;（6）改进Zelikovsk近似的分析;（7）构造相关问题的良好近似算法。

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