A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
From MaRDI portal
Publication:5874514
DOI10.4230/LIPICS.ESA.2020.44OpenAlexW3022560480MaRDI QIDQ5874514FDOQ5874514
Authors: Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, Hadas Shachnai 
Publication date: 7 February 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2020.44
Cites Work
- A threshold of ln n for approximating set cover
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- Bin packing can be solved within 1+epsilon in linear time
- The budgeted maximum coverage problem
- Maximizing a monotone submodular function subject to a matroid constraint
- Dependent rounding and its applications to approximation algorithms
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- Parameterized approximation scheme for the multiple knapsack problem
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- A note on maximizing a submodular set function subject to a knapsack constraint
- Optimal approximation for the submodular welfare problem in the value oracle model
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Symmetry and approximability of submodular maximization problems
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Submodular maximization with cardinality constraints
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)
