亚洲成年一级|甜心烊烊是麻豆传媒的吗|爱豆传媒凌萱是谁扮演的|91制片厂美凉子|萝莉社app链接|麻豆映画影视传媒网址|久久亚洲综合国产精品99麻豆精品福利|天美麻豆星空传媒|嘉尚传媒旗下爱豆有谁|91大神精品一区,亚洲成年激情,国产福利免费网,国产传媒91麻豆

報告題目：Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

主講人：李建平教授 （云南大學）      

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

地點：北院卓遠樓305會議室      

主辦單位：統(tǒng)計與數(shù)學學院

      摘要：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.

      主講人簡介：    

李建平，教授,，博士生導師,，法國巴黎南大學計算機科學專業(yè)博士。云南省“百人計劃”入選者,，云南省教學名師,，云南省中青年學術(shù)和技術(shù)帶頭人，云南省有突出貢獻專家,。研究領(lǐng)域：組合最優(yōu)化,、離散數(shù)學及理論計算機科學。云南省高?！靶畔⑴c計算科學專業(yè)教學團隊”帶頭人,，國家級和省級雙語教學示范課程“離散數(shù)學”負責人。