A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
From MaRDI portal
Publication:5874514
Cites work
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- A note on maximizing a submodular set function subject to a knapsack constraint
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- A threshold of ln n for approximating set cover
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Bin packing can be solved within 1+epsilon in linear time
- Dependent rounding and its applications to approximation algorithms
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Optimal approximation for the submodular welfare problem in the value oracle model
- Parameterized approximation scheme for the multiple knapsack problem
- Submodular maximization with cardinality constraints
- Symmetry and approximability of submodular maximization problems
- The budgeted maximum coverage problem
Cited in
(2)
This page was built for publication: A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874514)
