Symmetry and approximability of submodular maximization problems
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(32)- A note on the minimization of symmetric and general submodular functions
- Robust monotone submodular function maximization
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- Measured continuous greedy with differential privacy
- Approximation algorithms for vertex happiness
- Online risk-averse submodular maximization
- Robust monotone submodular function maximization
- Streaming algorithms for submodular function maximization
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- Improved inapproximability for submodular maximization
- Simultaneous approximation of multi-criteria submodular function maximization
- scientific article; zbMATH DE number 7255156 (Why is no real title available?)
- Online submodular maximization with preemption
- Multi-agent submodular optimization
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- The power of subsampling in submodular maximization
- Constrained submodular maximization via a nonsymmetric technique
- Submodular Maximization Through the Lens of Linear Programming
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- From query complexity to computational complexity
- An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
- Submodular Optimization with Contention Resolution Extensions.
- The Limitations of Optimization from Samples
- Weakly Submodular Function Maximization Using Local Submodularity Ratio.
- On maximizing sums of non-monotone submodular and linear functions
- Regularized nonmonotone submodular maximization
- Optimal streaming algorithms for submodular maximization with cardinality constraints
- Separating coverage and submodular: maximization subject to a cardinality constraint
- Monotone submodular multiway partition
- Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case
This page was built for publication: Symmetry and approximability of submodular maximization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2839179)
