学术报告：An Efficient Greedy+Singleton Approximation Algorithm for k-Submodular Knapsack Maximization

报告时间：6月3日（星期一）上午10:00-12:00

报告地点：沙河校区，二教109

报告人：唐中正，北京邮电大学理学院，副教授

报告摘要：A k-submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k-submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O(n2k). We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k-submodular functions, and prove an approximation ratio of 0.219.

报告人简介：唐中正博士，北京邮电大学理学院副教授，硕士生导师。2020年博士毕业于中科院数学与系统科学研究院，同年联合培养博士毕业于香港城市大学。主要从事组合优化和图论方面的理论与应用研究。