报告题目：Greedy+Max: An Efficient Approximation Algorithms for k-Submodular Knapsack Maximization

报 告 人：王晨豪 北京师范大学珠海校区人工智能与未来网络研究院

报告摘要：A k-submodular function is a generalization of submodular functions that takes k disjoint subsets as input and outputs a real value. It captures many problems in combinatorial optimization and machine leaning such as influence maximization, sensor placement, feature selection, etc. In this paper, we consider the monotone k-submodular maximization problem under a knapsack constraint, and explore the performance guarantee of a greedy-based algorithm, Greedy+Max, which adds the best feasible item to every partial greedy solution.  We prove that this algorithm achieves an approximation ratio of at least 1/3.

报告人简介：王晨豪，男，现任北京师范大学珠海校区人工智能与未来网络研究院特聘副研究员，BNU-HKBU联合国际学院（UIC）理工科技学部计算机科学与技术系助理教授。在中国科学院数学与系统科学研究院应用数学研究所获得理学博士学位（运筹学专业），并在香港城市大学电脑科学系获得哲学博士学位（联合培养）。此后，在美国内布拉斯加林肯大学和日本九州大学从事博士后研究。研究兴趣包括算法、AI、计算经济学及相关领域，特别是计算机科学与经济学交叉领域中优化和博弈问题的算法和机制设计。已在高水平国际会议和期刊上发表论文20余篇，其中CCF A/B类论文10余篇。

报告时间：2023年7月2日 15:00-16:30

报告地点：文渊楼 B208

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