Approximation of Steiner Minimum Trees and Applications

Steiner最小树的近似及其应用

• 批准号: 9530306
• 负责人: Ding-Zhu Du
• 金额: $ 12.5万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-08-15 至 2000-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9530306&HistoricalAwards=false
• 关键词: Approximation; Steiner; Minimum; Trees; 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.***

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