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

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

      地 点：腾讯线上会议号：274 709 032

报告摘要：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 polynomial-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 facility location and an important lemma proved by some techniques of computational geometry, we can provide a $1.214$-approximation algorithm to solve the $1$-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time $O(n^3\log n)$.

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