报告题目：星集填充问题的若干近似算法

报告摘要：星图是由一个中心及若干个叶子构成的特殊二部图，形如K1,i（也称为i-星）。给定图G以及一个星图集合H，图G的H-填充是G的一个顶点不交的子图集合，使得每一个子图均同构于星集H中的某个元素。包含在H-填充中的顶点称为被H-填充覆盖。H-填充问题就是要寻找G的一个H-填充使其覆盖的顶点数最多。特别地，t+-星集填充问题是指H由包含至少t(≥2)个叶子的全部星图构成的情形，T/t-星集填充问题是指H由除了K1,t以外包含2到T(>t)个叶子的全部星图构成的情形，两者均为强NP-难的。本文基于局部改进策略，设计了t+-星集填充问题的第一个近似算法，其近似比不超过(t+2)/2；当t=2时，基于生成森林切割的思想可以得到9/5-近似算法，而增加局部改进策略能够获得5/3-近似算法，好于已有结果。对T/2-星集填充问题，设计了近似比为10/7的算法，同样改进了已有最好结果（3/2-近似算法）。

报告人简介：张安，浙江大学博士（后），杭州电子科技大学教授、博士生导师。中国运筹学会排序分会理事、数学规划分会理事。主要研究排序、图论算法与计算复杂性。在Algorithmica, EJOR, TCS, ORL, DAM等期刊上发表论文40余篇，主持国家自然科学基金3项、浙江省自然科学基金2项，获得浙江省高校优秀科研成果二等奖、长三角地区运筹与控制论坛优秀论文二等奖。

报告时间：2023年10月14日09:00-10:00

报告地点：武之楼 308