Paper Info
Title
Submodular maximization by simulated annealing
Abstract
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.
Year
DOI
Venue
2011
10.5555/2133036.2133119
SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms San Francisco California January, 2011
Keywords
DocType
Volume
matroid base constraint,unconstrained submodular maximization,submodular set function,value oracle model,matroid independence constraint,simulated annealing,submodular maximization,disjoint base,cardinality constraint,submodular maximization subject,constant-factor approximation,randomized algorithms,leader election,distributed computing
Conference
abs/1007.1632
ISBN
Citations 
PageRank 
978-1-61197-251-1
36
1.72
References 
Authors
23
2
Name
Order
Citations
PageRank
Shayan Oveis Gharan132326.63
Jan Vondrák288847.94