Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-21
Computer Science
Data Structures and Algorithms
The conference version of this paper appeared in IEEE FOCS 2009. Unfortunately there was an error in the main theorem of the F
Scientific paper
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, and implies several new ones. In particular, we prove that there is no constant-factor approximation for the problem of maximizing a non-negative submodular function over the bases of a matroid. We also provide a closely matching approximation algorithm for this problem.
No associations
LandOfFree
Symmetry and approximability of submodular maximization problems 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 Symmetry and approximability of submodular maximization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetry and approximability of submodular maximization problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-85847