Submodular Maximization Through the Lens of Linear Programming
From MaRDI portal
Publication:5108239
Abstract: The simplex algorithm for linear programming is based on the fact that any local optimum with respect to the polyhedral neighborhood is also a global optimum. We show that a similar result carries over to submodular maximization. In particular, every local optimum of a constrained monotone submodular maximization problem yields a -approximation, and we also present an appropriate extension to the non-monotone setting. However, reaching a local optimum quickly is a non-trivial task. Moreover, we describe a fast and very general local search procedure that applies to a wide range of constraint families, and unifies as well as extends previous methods. In our framework, we match known approximation guarantees while disentangling and simplifying previous approaches. Moreover, despite its generality, we are able to show that our local search procedure is slightly faster than previous specialized methods. Furthermore, we resolve an open question on the relation between linear optimization and submodular maximization; namely, whether a linear optimization oracle may be enough to obtain strong approximation algorithms for submodular maximization. We show that this is not the case by providing an example of a constraint family on a ground set of size for which, if only given a linear optimization oracle, any algorithm for submodular maximization with a polynomial number of calls to the linear optimization oracle will have an approximation ratio of only .
Recommendations
- Maximizing submodular set functions subject to multiple linear constraints
- scientific article; zbMATH DE number 4137537
- Efficient Submodular Function Maximization under Linear Packing Constraints
- Maximizing a class of submodular utility functions
- Maximization of submodular functions: theory and enumeration algorithms
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Techniques for submodular maximization
- Submodular functions: optimization and approximation
Cites work
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
- A note on maximizing a submodular set function subject to a knapsack constraint
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- An analysis of approximations for maximizing submodular set functions—I
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Combinatorial auctions with decreasing marginal utilities
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Constrained submodular maximization via a nonsymmetric technique
- Deterministic algorithms for submodular maximization problems
- Improved approximations for \(k\)-exchange systems (extended abstract)
- Maximizing Non-monotone Submodular Functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Multi-budgeted matchings and matroid intersection via dependent rounding
- Non-monotone submodular maximization under matroid and knapsack constraints
- Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
- On the complexity of approximating \(k\)-set packing
- Optimal approximation for the submodular welfare problem in the value oracle model
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Reducibility among combinatorial problems
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization over multiple matroids via generalized exchange properties
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Symmetry and approximability of submodular maximization problems
Cited in
(6)- Sequence independent lifting for a set of submodular maximization problems
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- Lexicographically Optimal Base of a Submodular System with respect to a Weight Vector
- Efficient Submodular Function Maximization under Linear Packing Constraints
- Correction to: ``Guess free maximization of submodular and linear sums
- Note on pseudolattices, lattices and submodular linear programs
This page was built for publication: Submodular Maximization Through the Lens of Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108239)
