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

报 告 人：张昭，浙江师范大学

报告摘要：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项国家自然科学联合基金重点项目。曾获国家自然科学优秀青年基金，入选教育部新世纪优秀人才支持计划，新疆科技进步一等奖等。第八届国务院学位办数学学科评议组成员、中国运筹学会常务理事等。

报告时间：2023年3月31日 9:00-10:00

报告地点：文渊楼 B119

主办单位：伟德国际1946源自英国