Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
From MaRDI portal
Publication:6170425
DOI10.1137/19m125515xMaRDI QIDQ6170425
Moran Feldman, Mohit Garg, Niv Buchbinder
Publication date: 10 August 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Combinatorics in computer science (68R05) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An exchange theorem for bases of matroids
- Online Submodular Welfare Maximization
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Submodular Max-SAT
- 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
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Deterministic Algorithms for Submodular Maximization Problems
- A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
- Constrained Submodular Maximization via a Nonsymmetric Technique
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
- Submodular Maximization with Cardinality Constraints
- Fast algorithms for maximizing submodular functions
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- Comments on bases in dependence structures
- A Multiple Exchange Property for Bases
- Online submodular maximization: beating 1/2 made simple
This page was built for publication: Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
