题目：An improved approximation algorithm for maximizing a DR-submodular function over a convex set

报告人：徐大川(北京工业大学)

时间：2022年7月30日(星期六) 9:00

腾讯会议：293-401-095

摘要：Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arisingfrom many applications in combinatorial optimization and machine learning. While it is highly desirable to designefficient approximation algorithms under this general setting where neither the objective function is monotonicnor the feasible set is down-closed, unfortunately, Vondrak (2013) shows that such a problem admits no constantapproximation under the value oracle model. Our main contribution is to present a 41 = 0.25-approximationFrank-Wolfe type of algorithm with a sub-exponential time-complexity under the value oracle model, improvinga previous approximation ratio of 1 3√3 ≈ 0.1924 with the same order of time-complexity by Durr et al. (2021).In the process, we also introduce a few new ideas of independent interests, including the exponential integratormethod to discretize the ordinary differential equation (ODE) in the continuous-time Frank-Wolfe algorithm, andthe Lyapunov function approach to streamline the analysis of the approximation ratio and/or the convergence ratein both the continuous and discrete settings. (Joint work with Donglei Du, Zhicheng Liu, Chenchen Wu, andYang Zhou)

个人简介：徐大川，北京工业大学理学部运筹学与控制论责任教授，数学/统计学博士生导师。北京工业大学区块链研究中心副主任。2002年于中国科学院数学与系统科学研究院获得博士学位。研究兴趣包括：机器学习与优化，近似算法等。中国运筹学会数学规划分会理事长，中国运筹学会宣传工作委员会主任，北京运筹学会副理事长。《Asia-Pacific Journal of Operational Research》、《Applied Mathematics and Computation》、《Journal of the Operations Research Society of China》、《Discrete Mathematics, Algorithms and Applications》、《Statistics, Optimization and Information Computing》、《运筹与管理》编委，《Algorithmica》、《Journal of Combinatorial Optimization》客座编委。ISMP2022组委会秘书长，COCOA 21，COCOON 17程序委员会主席,LOD 20, AAIM 20，LION 14程序委员会委员。曾获得中国运筹学会青年论文奖一等奖、中国运筹学会运筹新人奖。主持国家自然科学基金青年基金1项、面上项目4项、天元基金1项、重点项目子课题1项、重点项目1项。出版学术专著1部，在《Mathematical Programming》、《Operations Research》、《INFORMS Journal on Computing》、《Algorithmica》等发表学术论文100余篇。