报告题目：Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

主讲人：李建平教授 （云南大学）      

时间：2021年4月12日（周一）15:00 p.m.

地点：北院卓远楼305会议室      

主办单位：统计与数学学院

      摘要：In this talk, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem), which is a variant of the Euclidean capacitated minimum Steiner tree problem and defined as follows. Given a set $X=\{r_{1}, r_{2}, \ldots, r_{n}\}$ of $n$ terminals in $\mathbb{R}^2$, a demand function $d:X \rightarrow \mathbb{Z}_0^+$ and a positive integer $C$, we are asked to determine the location of a line $l$ and a Steiner tree $T_l$ to interconnect these $n$ terminals in $X$ and at least one point located on this line $l$ such that the total demand of terminals in each maximal subtree (of $T_l$) connected to the line $l$, which is within the same side out of this line $l$, does not exceed the capacity $C$, the objective is to minimize total weight $\sum_{e\in T_l}w(e)$ of such a Steiner tree $T_l$ among all line-capacitated Steiner trees mentioned-above, where weight $w(e)=0$ if two endpoints of that edge $e\in T_l$ are located on the line $l$ and otherwise weight $w(e)$ is the Euclidean distance between two endpoints of that edge $e\in T_l$. In addition, when $\sum_{r\in X} d(r) \leq C$ holds and this line $l$ is as an input in $\mathbb{R}^2$, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem).We obtain three main results. (1) Given a $\rho_{st}$-approximation algorithm to solve the Euclidean minimum Steiner tree problem and a $\rho_{1Lf}$-approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a $(\rho_{st}\rho_{1Lf}+2)$-approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal $r\in X$ is less than $\frac{C}{2}$, we provide a $(\rho_{1Lf}+2)$-approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal $r\in X$ is at least $\frac{C}{2}$, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem.Keywords: Combinatorial optimization; Locations of lines; Line-capacitated Steiner trees; Approximation algorithms; Exact algorithms.

      主讲人简介：    

李建平，教授，博士生导师，法国巴黎南大学计算机科学专业博士。云南省“百人计划”入选者，云南省教学名师，云南省中青年学术和技术带头人，云南省有突出贡献专家。研究领域：组合最优化、离散数学及理论计算机科学。云南省高校“信息与计算科学专业教学团队”带头人，国家级和省级双语教学示范课程“离散数学”负责人。