Submodular maximization by simulated annealing

By Shayan Oveis Gharan, Jan Vondr'ak. 2010

191 citations recorded by the source corpus.

We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [9] showed a 2/5-approximation for the unconstrained problem and also proved that no approximation better than 1/2 is possible in the value oracle model. Constant-factor approximation has been also known for submodular maximization subject to a matroid independence constraint (a factor of 0.309 [33]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number ν is bounded away from 1 (a 1/4-approximation assuming that ν ≥ 2 [33]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of simulated annealing. We prove that this algorithm achieves improved approximation for two problems: a 0.41-approximation for unconstrained submodular maximization, and a 0.325-approximation for submodular maximization subject to a matroid independence constraint. On the hardness side, we show that in the value oracle model it is impossible to achieve a 0.478-approximation for submodular maximization subject to a matroid independence constraint, or a 0.394-approximation subject to a matroid base constraint in matroids with two disjoint bases. Even for the special case of cardinality constraint, we prove it is impossible to achieve a 0.491-approximation. (Previously it was conceivable that a 1/2-approximation exists for these problems.) It is still an open question whether a 1/2-approximation is possible for unconstrained submodular maximization.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, methodology): “[47] showed that even nonmonotone submodular functions can be approximately maximized in polynomial time using a local search algorithm, and a growing body of research has focused on extending this result in a variety of ways [25, 48, 49, 56, 90, 153].”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, unknown): “Gharan and Vondrák [14] showed that an extension of the last method, known as simulated annealing, can provide an improved approximation of roughly 0.41.”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “Among combinatorial methods, modified greedy, local search and simulated annealing algorithms provide certain constant factor guarantees [16, 17, 18] and have been recently extended to optimization under knapsack and matroid constraints [19, 20].”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, background): “491] (Buchbinder & Feldman, 2019; Gharan & Vondrák, 2011).”
Submodular function maximization via the multilinear relaxation and contention resolution schemes (2011, methodology): “478approximation in the value oracle model, even in the special case of a matroid polytope, also due to [30].”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, methodology): “The best of the three (with respect to its approximation guarantee) uses a simulated annealing technique [21].”
Fast algorithms for maximizing submodular functions (2014, methodology): “) Let us mention some other recent advances and their limitations in terms of running time: • The notion of multilinear relaxation has been used to achieve an optimal (1−1/e)-approximation for submodular maximization subject to a matroid constraint [2], as well as improved approximations for more ge”
Submodular Maximization with Cardinality Constraints (2014, methodology): “For both variants of the cardinality constraint, [25] presented a hardness of 0.”
Submodular Function Maximization (2014, background): “In particular, Gharan and Vondr´ak (2011) show that a simulated annealing algorithm is guaranteed to obtain a 0 .”
Non-monotone Submodular Maximization in Exponentially Fewer Iterations (2018, unknown): “Non-monotone submodular maximization is well-studied [FMV11, LMNS09, GRST10, FNS11, GV11, BFNS14, CJV15, MBK16, EN16], particularly under a cardinality constraint [LMNS09, GRST10, GV11, BFNS14, MBK16].”