报告题目：求解直线欧氏最小斯坦纳树问题的近似算法

报 告 人：李建平教授（云南大学）

报告时间：2021年11月19日  14:30-16:00

报告地点：腾讯会议（274709032）

报告摘要：

In this talk, we consider the $1$-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem. We obtain the following two main results. (1) Using a polynomia-time exact algorithm to find a constrained Euclidean minimum Steiner tree， we can design a $1.214$-approximation algorithm to solve the $1$-line-fixed Euclidean minimum Steiner tree problem, and this algorithm runs in time $O(n\log n)$; (2) Using the algorithm designed in (1) for many times, a technique of finding linear facilit location and an important lemma proved by some techniques of computational geometry, we can provide a $1.214$ -approximation algorithm to solve the $15-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time $O(n^3log n)$.

报告人简介：

李建平博士是云南大学教授，二级岗位。主要从事运筹学、组合最优化、计算机科学与技术等领域研究与教学。“云岭学者”和云南省首批“百名海外高层次人才引进计划”入选者，云南省中青年学术技术带头人，获云南省科学技术奖励2项，云南省有突出贡献优秀专业技术人才奖励1项。主持完成国家自然科学基金项目7项及省级重点项目等8项，作为学术带头人承担《云南大学运筹学省创新团队》建设项目1项，云南省高校计算理论与应用科技创新团队建设项目1项。