Submodular Maximization Through the Lens of Linear Programming
From MaRDI portal
Publication:5108239
DOI10.1287/moor.2018.0965zbMath1437.90096arXiv1711.11316OpenAlexW2965479381MaRDI QIDQ5108239
Simon Bruggmann, Rico Zenklusen
Publication date: 30 April 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.11316
Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- A note on maximizing a submodular set function subject to a knapsack constraint
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- On the complexity of approximating \(k\)-set packing
- Combinatorial auctions with decreasing marginal utilities
- Symmetry and Approximability of Submodular Maximization Problems
- Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Improved Approximations for k-Exchange Systems
- Maximizing Non-monotone Submodular Functions
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Deterministic Algorithms for Submodular Maximization Problems
- Reducibility among Combinatorial Problems
- Constrained Submodular Maximization via a Nonsymmetric Technique
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
This page was built for publication: Submodular Maximization Through the Lens of Linear Programming
