报告题目：Approximation Algorithms for Minimum Weight Connected Dominating Set

报告人：张昭 特聘教授（浙江师范大学）

报告时间：2023 年 6 月 21 日（星期三） 16:00-17:00

报告地点：海山楼（创新园大厦）A1410

校内联系人：王毅 教授

报告摘要: A connected dominating set (CDS) of a graph G is a vertex set C such that every vertex in V(G)\C has at least one neighbor in C and the subgraph of G induced by C is connected. The goal of the minimum weight connected dominating set problem (MinWCDS) is to find a CDS with the minimum total vertex weight. The best previously known approximation ratio for MinWCDS is (1.35+ε)ln(n), due to Guha and Khuller in 1999. In this talk, I’ll introduce our recent result which breaks the barrier of ln(n), improving the ratio to 2ln∆, where ∆ is the maximum degree of the graph (note that in general, ∆ is much smaller than n).

报告人简介：张昭，浙江师范大学杰出教授，浙江省“钱江学者”特聘教授。主要研究方向为离散优化算法设计与分析，发表学术论文200余篇，被SCI索引140余篇。主持完成了4项国家自然科学基金项目和4项教育部项目，目前主持1项国家自然科学联合基金重点项目。曾获国家自然科学优秀青年基金，入选教育部新世纪优秀人才支持计划，新疆科技进步一等奖等。第八届国务院学位办数学学科评议组成员、中国运筹学会常务理事、中国运筹学会数学规划分会副理事长等。