报告题目：Partial Inverse Min-Max Spanning Tree Problem under the Weighted Bottleneck Hamming Distance

报告人：李宪越，兰州大学

报告时间：2023年10月23日（周一）9:30-10:30

报告地点：20-308

报告摘要：Min-max spanning tree problem is a classical problem in combinatorial optimization. Its purpose is to find a spanning tree to minimize its maximum edge in a given edge weighted graph. Given a connected graph, an edge weight vector and a forest, the partial inverse min-max spanning tree problem (PIMMST) is to find a new weighted vector, so that the forest can be extended into a min-max spanning tree with respect to new weight vector and the gap between the two vectors is minimized. In this paper, we research PIMMST under the weighted bottleneck Hamming distance. Firstly, we study PIMMST with value of optimal tree restriction, a variant of PIMMST, and show that this problem can be solved in strongly polynomial time. Then, by characterizing the properties of the value of optimal tree, we present first polynomial algorithm for PIMMST under the weighted bottleneck Hamming distance. Finally, by giving a necessary and sufficient condition to determine the feasible solution of this problem, we present a better algorithm for this problem. Moreover, we show that these algorithms can be generalized to solve these problems with capacitated constraint.

报告人简介：李宪越，兰州大学数学与统计学院副教授，硕士生导师。主要从事组合优化、近似算法设计与分析和图论及其应用的研究。中国运筹学会组织工作委员会副秘书长、数学规划分会第八届理事会(2023-2027)理事、组合图论分会第六届理事会(2023-2027)理事。2016-2018 年，连续三年担任了国家自然科学基金委员会数学天元基金全国“组合优化”研究生暑期学校助教。在 Journal of Global Optimization，IEEE/ACM Transactions on Networking，IEEE Transactions on Mobile Computing，IEEE Transactions on Services Computing，Journal of Combinatorial Optimization，Discrete Applied Mathematics，IEEE INFOCOM 等相关领域权威期刊和顶级会议上发表学术论文30余篇。目前主持国家自然科学基金面上项目1项，主持完成了国家自然科学基金青年基金1项、数学天元青年基金1项、国家数值风洞工程项目1项(国防类)、总装共用技术项目1项(国防类)。主要承担运筹学、图论等本科生课程及组合最优化、近似算法、图论等研究生课程。