报 告 人：李建平 教授
报告题目：1-line minimum Steiner trees andrelated problems
报告时间：2021年12月18日（周六）上午8:30-12:00
报告地点：腾讯会议（ID：687443789）
主办单位：数学与统计学院、科学技术研究院
报告人简介：
李建平，云南大学教授，主要从事运筹学、组合最优化、计算机科学与技术等领域研究与教学。“云岭学者”和云南省首批“百名海外高层次人才引进计划”入选者，云南省中青年学术技术带头人，获云南省科学技术奖励2项，云南省有突出贡献优秀专业技术人才奖励1项。主持完成国家自然科学基金项目7项及省级重点项目等8项，担任中国工业与应用数学学会图论组合及应用专业委员会副主任委员，中国运筹学会理事，云南省高等学校数学类教学指导委员会主任委员。在European Journal ofOperational Research, Journal of Global Optimization, Journal of CombinatorialOptimization, Theoretical Computer Science, Optimization Letters等国内外刊物发表学术论文。
报告摘要：
In this talk, weconsider the 1-line minimum Steiner tree problem, which is a variation of theEuclidean minimum Steiner tree problem and defined as follows. Given a set P={r1,r2,…, rn} of n points in theEuclidean plane R2, we are asked to findthe location of a line l and an Euclidean Steiner tree T(l) in R2such that at least one Steiner point is located at such a line l, the objectiveis to minimize total weight of such an Euclidean Steiner tree T(l), i.e., min{∑e∈T(l) w(e) |T(l) is anEuclidean Steiner tree as mentioned-above}, where we define weight w(e)=0 ifthe end-points u, v of each edge e=uv∈T(l)are both located at such a line l and otherwise we denote weight w(e) to be theEuclidean distance between u and v. Given a fixed line l as an input in R2,we refer this problem as the 1-line-fixed Euclidean minimum Steiner treeproblem; In addition, when Steiner points added are all located at such a fixedline l, we refer this problem as the constrained Euclidean minimum Steiner treeproblem. We provide other related problems.
We obtain the followingthree main results. (1) Using a polynomial-time exact algorithm to find a constrainedEuclidean minimum Steiner tree, we can design a 1.214-approximation algorithmto solve the 1-line-fixed Euclidean minimum Steiner tree problem, and thisalgorithm runs in time O(nlogn); (2) Using the algorithm designed in (1) formany times, a technique of finding linear facility location and an importantlemma proved by some techniques of computational geometry, we can provide a1.214-approximation algorithm to solve the 1-line Euclidean minimum Steinertree problem, and this new algorithm runs in time O(n3logn). (3) Wepresent other results to solve the related problems.
邀 请 人：苗正科