学校主页 加入收藏 English
当前位置: 首页 >> 通知公告 >> 正文 通知公告
龙马统数·见微知著大讲堂第66讲:An Efficient Greedy+Singleton Approximation Algorithm for k-Submodular Knapsack Maximization
来源:  点击次数: 次 发布时间:2024-05-28   编辑:统计与数学学院

学术报告: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年博士毕业于中科院数学与系统科学研究院,同年联合培养博士毕业于香港城市大学。主要从事组合优化和图论方面的理论与应用研究。

首页

          版权所有:中央财经大学统计与数学学院  
          地址:北京市昌平区沙河高教园中央财经大学沙河校区1号学院楼   邮政编码:102206   电 话:(010)61776184    
          邮箱:samofcufe@cufe.edu.cn    
         

学院公众号