An almost optimal approximation algorithm for monotone submodular multiple knapsack
From MaRDI portal
Publication:2071828
DOI10.1016/j.jcss.2021.11.005OpenAlexW3130543970MaRDI QIDQ2071828
Danny Raz, Ariel Kulik, Hadas Shachnai, Joseph (Seffi) Naor, Yaron Fairstein
Publication date: 31 January 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.12224
Cites Work
- Unnamed Item
- 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
- Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
- 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
- Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
This page was built for publication: An almost optimal approximation algorithm for monotone submodular multiple knapsack
