Unified Greedy Approximability beyond Submodular Maximization
From MaRDI portal
Publication:6141865
DOI10.1137/22m1526952OpenAlexW4390977331MaRDI QIDQ6141865
Publication date: 23 January 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/22m1526952
greedy algorithmindependence systemapproximation ratioaugmentabilitysubmodularity ratiocardinality-constrained maximization
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Robust monotone submodular function maximization
- General bounds for incremental maximization
- The Design of Approximation Algorithms
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Greedy algorithm and symmetric matroids
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of the Greedy Heuristic for Independence Systems
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Structured Robust Submodular Maximization: Offline and Online Algorithms
- Non-monotone submodular maximization under matroid and knapsack constraints
- Submodular Maximization with Cardinality Constraints
- Greedy in Approximation Algorithms
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Matroids and the greedy algorithm
- A THEOREM ON INDEPENDENCE RELATIONS
- Combinatorial optimization. Theory and algorithms.
- Unified greedy approximability beyond submodular maximization
This page was built for publication: Unified Greedy Approximability beyond Submodular Maximization
