应用数学青年讨论班(午餐会)--Submodular maximization: maximizing non-monotone submodular functions under matroid and knapsack constraints
报告人：高艺炜（中国科学院计算技术研究所）
时间：2026-04-08 12:00-13:30
地点：智华楼四元厅
摘要：
Submodular maximization is a central problem in combinatorial optimization and theoretical computer science, with broad applications in areas such as machine learning, economics, and network design. Despite significant progress, many of the best-known algorithms with strong performance guarantees rely on randomness. In this talk, Yiwei Gao will present two deterministic algorithms proposed in their recent work for maximizing non-monotone submodular functions under matroid and knapsack constraints. Both algorithms achieve improved approximation guarantees compared to all previously known deterministic algorithms for these settings, while maintaining polynomial query complexity.
报告人简介：
高艺炜是中国科学院计算技术研究所量子计算与算法理论实验室的博士生，导师是孙晓明研究员。他于2022年获得北京师范大学数学科学学院学士学位。他的研究方向集中在带约束的次模函数最大化问题。
欢迎大家参与4月8日（星期三）的午餐会。报告时间是12:15-13:30，午餐于12:00开始提供。请有意参与的老师和同学在4月7日17:00前填写以下问卷 //v.wjx.cn/vm/wFUaQwJ.aspx。
