An almost optimal approximation algorithm for monotone submodular multiple knapsack

DOI10.1016/j.jcss.2021.11.005MaRDI 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

zbMATH Keywords

approximation algorithms; monotone submodular functions; multiple Knapsack constraint

Mathematics Subject Classification ID

68-XX: Computer science

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