解决1-线最小线段斯坦纳树问题的近似算法
科研大讨论系列报告
报告题目(Title):解决1-线最小线段斯坦纳树问题的近似算法
报告人(Speaker):李建平教授 (云南大学)
地点(Place):腾讯会议 ID:216 400 316
时间(Time):2023 年 9 月 8 日(周五) 14:30--15:30
邀请人(Inviter):徐敏
报告摘要
In this talk, we address the $1$-line minimum Steiner tree of line segments (1L-MStT-LS) problem. Specifically, given a set $S$ of $n$ disjoint line segments in $\mathbb{R}^2$, we are asked to find the location of a line $l$ and a set $E_l$ of necessary line segments in $\mathbb{R}^2$ such that a graph consisting of all line segments in $S\cup E_l$ plus this line $l$, simply denoted by $T_l=(S, l, E_l)$, becomes a Steiner tree, the objective is to minimize total weight of line segments ({\it i.e.}, edges) in $E_l$ among all such Steiner trees mentioned-above, {\it i.e.}, $\min\{\sum_{e\in E_l} w(e)$ $\vert $ $T_l=(S, l, E_l)$ is a tree mentioned-above$\}$, where weight $w(e)$ is the Euclidean distance between the two endpoints of that segment $e\in E_l$. For convenience, we refer to such a tree $T_l$ as a $1$-line (minimum) Steiner tree of line segments. Similarly, we are asked to find a set $E_0$ of necessary line segments in $\mathbb{R}^2$ such that a graph only consisting of all line segments in $S\cup E_0$, simply denoted by $T_S=(S,E_0)$, becomes a Steiner tree in $\mathbb{R}^2$, the objective is to minimize total weight of line segments ({\it i.e.}, edges) in $E_0$ among all such Steiner trees mentioned-above, we refer to this problem as the minimum Steiner tree of line segments (MStT-LS) problem. In addition, when two endpoints of each line segment in $E_0$ needs to be located on two different line segments in $S$, respectively, we refer to that problem as the minimum spanning tree of line segments (MST-LS) problem. Furthermore, when each line segment in $S$ degenerates to be a point, the MStT-LS problem becomes the Euclidean minimum Steiner tree problem. We obtain three main results. (1) Using techniques of computational geometry to construct a Voronoi diagram of line segments, we design an exact algorithm in time $O(n\log n)$ to solve the MST-LS problem; (2) we show that the algorithm designed in (1) is a $1.214$-approximation algorithm to solve the MStT-LS problem; (3) using the combination of the algorithm designed in (1) as a subroutine for many times, a technique of finding linear facility location and a key lemma proved by techniques of computational geometry, we present a $1.214$-approximation algorithm in time $O(n^3\log n)$ to solve the 1L-MStT-LS problem.
主讲人简介
李建平,教授,博士生导师,法国巴黎南大学计算机科学专业博士。云南省“兴滇英才计划”云岭学者,云南省首届“百名海外高层次人才引进计划”入选者,云南省教学名师,云南省中青年学术和技术带头人,云南省有突出贡献专家,全国宝钢优秀教师奖获得者;云南省运筹学创新团队带头人,云南省高校“信息与计算科学专业教学团队”带头人,国家级双语教学示范课程“离散数学”负责人。
研究领域:组合最优化、离散数学及理论计算机科学。