An almost optimal approximation algorithm for monotone submodular multiple knapsack

DOI10.1016/J.JCSS.2021.11.005MaRDI QIDQ2071828zbMATH OpenOpenAlexFDO

Authors Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, Hadas Shachnai

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 algorithmsmonotone submodular functionsmultiple Knapsack constraint

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Non-monotone submodular maximization under matroid and knapsack constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints

Cites work

• A Fast Approximation Scheme for the Multiple Knapsack Problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A threshold of ln n for approximating set cover
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Bin packing can be solved within 1+epsilon in linear time
• Dependent rounding and its applications to approximation algorithms
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Optimal approximation for the submodular welfare problem in the value oracle model
• Parameterized approximation scheme for the multiple knapsack problem
• Submodular maximization with cardinality constraints
• Symmetry and approximability of submodular maximization problems
• The budgeted maximum coverage problem

Cited in

(5)

• Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
• Generalized assignment via submodular optimization with reserved capacity
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• New approximations for monotone submodular maximization with knapsack constraint

This page was built for publication: An almost optimal approximation algorithm for monotone submodular multiple knapsack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2071828)