Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late 1970’s. A central technique in this field is to approximately optimize the multilinear extension of the submodular objective, and then round the solution. The use of this technique requires a solver able to approximately maximize multilinear extensions. Following a long line of work, Buchbinder and Feldman(2019) described such a solver guaranteeing 0.385-approximation for down-closed constraints, while Oveis Gharan and Vondrak (2011) showed that no solver can guarantee better than 0.478-approximation. In this talk, I will present a new solver guaranteeing 0.401-approximation, which significantly reduces the gap between the best known solver and the inapproximability result. The design and analysis of the new solver are based on a novel bound that we have proved for DR-submodular functions, and might be of independent interest.
Based on a joint work with Niv Buchbinder.
