首页

学术报告

当前位置: 首页 >> 正文

科学计算系列报告:求解直线欧氏最小斯坦纳树问题的近似算法

发布人:日期:2021年11月17日 11:12浏览数:

      报告人:李建平 教授(云南大学)

      时 间: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项















上一条:科学计算系列报告:轴对称物体X射线图像重建的正则化方法

下一条:分析团队系列报告:Quasiconformal geometry and removable sets for conformal mappings

【关闭】 打印    收藏