报告人：浙江师范大学 张昭教授
报告时间；2025年11月15日11:30
报告地点：科技园阳光楼南815
报告题目：Approximation Algorithm for Unrooted Prize-Collecting Forest with Multiple Components
摘要：
In this talk, I will introduce our work on a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with $K$ Components (URPCF$_K$) problem, which aims to find a forest with exactly $K$ connected components while minimizing the sum of the forest's weight and the penalties incurred by unspanned vertices. In particular, for $K=1$, the URPCF$_1$ problem is exactly the prize-collecting Steiner tree (PCST) problem, which has received extensive studies. Unlike the PCST problem, whose unrooted version can be solved by transforming it into an unrooted version by guessing the root, the unrooted PCF$_K$ problem cannot be readily solved using its rooted analogue, because guessing its roots may lead to exponential time complexity for non-constant $K$. To address this challenge, we propose a rootless growing and rootless pruning algorithm. We also apply this algorithm to improve the approximation ratio for the Prize-Collecting Min-Sensor Sweep Cover problem (PCMinSSC) from 8 to 5.
报告人简介：
张昭，浙江师范大学杰出教授，主要研究方向为组合优化算法设计与分析，在MP, TON, INFORMS JOC, COLT等期刊会议发表学术论文250余篇。主持完成了5项国家自然科学基金项目（包括1项国家自然科学联合基金重点项目和1项国家优秀青年基金项目）、4项教育部项目（包括1项教育新世纪优秀人才项目）和1项浙江省重大项目。曾获新疆科技进步一等奖、浙江省“三八红旗手”、浙江省“师德楷模”称号等。现为第八届国务院学位办数学学科评议组成员、中国运筹学会常务理事、中国运筹学会数学规划分会副理事长、金华市女科技工作者协会会长等。
