Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	徐大川教授，北京工业大学理学部
Inviter:
Title:	An improved approximation algorithm for maximizing a DR-submodular function over a convex set
Time & Venue:	2022.04.26 15:00 - 16:00 腾讯会议： 417-248-509
Abstract:	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)