A refined analysis of submodular greedy
From MaRDI portal
Publication:2060587
DOI10.1016/j.orl.2021.04.006OpenAlexW3159636333MaRDI 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 (3)
Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ Energy-constrained geometric coverage problem ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
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
This page was built for publication: A refined analysis of submodular greedy