An almost optimal approximation algorithm for monotone submodular multiple knapsack
type: Item
instance of: scholarly article
title: An almost optimal approximation algorithm for monotone submodular multiple knapsack
author: Yaron Fairstein
author: Ariel Kulik
author: Joseph (Seffi) Naor
author: Danny Raz
author: Hadas Shachnai
published in: Journal of Computer and System Sciences
publication date: 2022-01-31T00:00:00Z
full work available at URL: https://arxiv.org/abs/2004.12224
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7466702
zbMATH Keywords: multiple Knapsack constraint
zbMATH Keywords: monotone submodular functions
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
OpenAlex ID: W3130543970
cites work: Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
cites work: Submodular Maximization with Cardinality Constraints
cites work: Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
cites work: Q5365101
cites work: Bin packing can be solved within 1+epsilon in linear time
cites work: Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
cites work: A threshold of ln n for approximating set cover
cites work: A Unified Continuous Greedy Algorithm for Submodular Maximization
cites work: Dependent rounding and its applications to approximation algorithms
cites work: Parameterized Approximation Scheme for the Multiple Knapsack Problem
cites work: A Fast Approximation Scheme for the Multiple Knapsack Problem
cites work: The budgeted maximum coverage problem
cites work: Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
cites work: Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
cites work: Best Algorithms for Approximating the Maximum of a Submodular Set Function
cites work: A note on maximizing a submodular set function subject to a knapsack constraint
cites work: Q3549686
cites work: Symmetry and approximability of submodular maximization problems
DOI: 10.1016/J.JCSS.2021.11.005
description: scientific article; zbMATH DE number 7466702