威廉希尔体育,威廉体育官方

首页

当前您的位置: 首页 > 学术讲座 > 正文

【4月12日】数学学术讲座

发布日期:2021-04-09点击: 发布人:统数学院

报告题目: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.


      主讲人简介:    

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