A refined analysis of submodular greedy
From MaRDI portal
Publication:2060587
DOI10.1016/j.orl.2021.04.006MaRDI QIDQ2060587
Ariel Kulik, Hadas Shachnai, Roy Schwartz
Publication date: 13 December 2021
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.12879
Related Items
Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm, Energy-constrained geometric coverage problem
Cites Work
- The generalized maximum coverage problem
- Comparison theorems for differential equations
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- A threshold of ln n for approximating set cover
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Fast algorithms for maximizing submodular functions
- Elements of Information Theory
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem