北京工业大学徐大川教授学术报告

发布者:周春宇发布时间:2022-07-11浏览次数:10

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

  

报告人简介:徐大川,北京工业大学教授,博导,中国运筹学会数学规划分会理事长、中国运筹学会宣传委员会主任、北京运筹学会副理事长。

  

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

  

报告摘要: Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arising from many applications in combinatorial optimization and machine learning. While it is highly desirable to design efficient approximation algorithms under this general setting where neither the objective function is monotonic nor the feasible set is down-closed, unfortunately, Vondrak (2013) shows that such a problem admits no constant approximation under the value oracle model. Our main contribution is to present a $\frac{1}{4}=0.25$-approximation Frank-Wolfe type of algorithm with a sub-exponential time-complexity under the value oracle model, improving a previous approximation ratio of $\frac{1}{3\sqrt{3}}\approx 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 integrator method to discretize the ordinary differential equation (ODE) in the continuous-time Frank-Wolfe algorithm, and the Lyapunov function approach to streamline the analysis of the approximation ratio and/or the convergence rate in both the continuous and discrete settings. (Joint work with Donglei Du, Zhicheng Liu, Chenchen Wu, and Yang Zhou)

  

会议地址:


 

返回原图
/