Submodular Maximization by Simulated Annealing

Details Submodular Maximization by Simulated Annealing Submodular Maximization by Simulated Annealing

2010-07-09

arxiv.org/abs/1007.1632v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [FOCS'07] 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 was also given for submodular maximization subject to a matroid independence constraint (a factor of 0.309 Vondrak [FOCS'09]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number is at least 2 (a 1/4-approximation, Vondrak [FOCS'09]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of {\em 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.

Affiliated with

Also associated with

No associations

Rating

Submodular Maximization by Simulated Annealing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Submodular Maximization by Simulated Annealing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodular Maximization by Simulated Annealing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645579