报告题目：On maximizing a monotone k-submodular function under a knapsack constraint

报 告 人：唐中正，北京邮电大学

报告摘要：We study the problem of maximizing a non-negative monotone k-submodular function f under a knapsack constraint, where a k-submodular function is a natural generalization of a submodular function to k dimensions. We present a deterministic 1/2(1-1/e)-approximation algorithm based on the result of Sviridenko (2004) on submodular knapsack maximization. We also consider the algorithm that returns the better solution between the single element of highest value and the result of the fully greedy algorithm, to which we refer as Greed +Singleton, and prove an approximation ratio 1/4 (1-1/e) .

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

报告时间：2022年10月10日 19:00-20:00

报告地点：腾讯会议ID：603-632-716

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