Optimal approximation for submodular and supermodular optimization with bounded curvature

By Maxim Sviridenko, Jan Vondr'ak, Justin Ward. 2013

292 citations recorded by the source corpus.

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1 − c/e)-approximation --- the first improvement over the greedy (1 − e--c)/c-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Optimization & Training

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, methodology): “The reweighted input change objective F is closely related to the column subset selection objective (the latter is a special case of F where W +1 is the identity matrix), whose total curvature was shown to be related to the condition number of A (cid:96) in [Sviridenko et al., 2017].”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, background): “However, it is possible to improve upon this bound when the data obeys some additional guarantees [Conforti and Cornuéjols, 1984; Vondrák, 2010; Sviridenko et al., 2015].”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, methodology): “Recently, Sviridenko et al. (2015) present a notion of curvature for monotone non-submodular functions.”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, background): “The problem of maximizing g + ` for non-negative monotone submodular g and an (arbitrary) modular function ` under cardinality constraints was first considered in (Sviridenko et al., 2017), who gave a randomized polynomial time algorithm which outputs a set S such that g(S) + `(S) ≥ (1− 1/e)g(OPT ) ”
Approximation Guarantees for Adaptive Sampling (2018, background): “Curvature is a well-studied concept in the context of submodular optimization (Conforti & Cornuéjols, 1984; Vondrák, 2010; Iyer & Bilmes, 2013; Iyer et al., 2013; Sviridenko et al., 2015; Balkanski et al., 2016).”