A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
From MaRDI portal
Publication:5874514
DOI10.4230/LIPIcs.ESA.2020.44OpenAlexW3022560480MaRDI QIDQ5874514
Danny Raz, Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Hadas Shachnai
Publication date: 7 February 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2020.44
Related Items (1)
Cites Work
- Unnamed Item
- Bin packing can be solved within 1+epsilon in linear time
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- Symmetry and Approximability of Submodular Maximization Problems
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Dependent rounding and its applications to approximation algorithms
- Parameterized Approximation Scheme for the Multiple Knapsack Problem
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Submodular Maximization with Cardinality Constraints
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- A Unified Continuous Greedy Algorithm for Submodular Maximization
This page was built for publication: A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
