数学与计算机交叉学科学术报告

报 告 人：堵丁柱教授（美国德克萨斯大学达拉斯分校）

报告题目：Min-Max Set Cover and Group Set Cover

报告时间：2019年9月23日（星期一）15:30

报告地点：数计学院第一会议室

报告摘要：There are three optimization problems about set covers, the maximum coverage problem, the minimum set cover problem, and the min-max set cover problem.  For all of them, the greed algorithm has the best possible performance ratio among all polynomial-time approximation.  However, this is not true for group set cover. In this talk, a comparison is studied between set cover and group set cover. This comparison will explore some interesting open problems for our future research.