Generalized assignment via submodular optimization with reserved capacity

DOI10.4230/LIPICS.ESA.2019.69MaRDI QIDQ5075815zbMATH OpenFDO

Authors Ariel Kulik, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1907.01745

zbMATH Keywords

approximation algorithmsgroup generalized assignment problemknapsack constraintssubmodular maximization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• All-or-nothing generalized assignment with application to scheduling advertising campaigns
• All-or-nothing generalized assignment with application to scheduling advertising campaigns
• Maximizing a monotone submodular function subject to a matroid constraint
• An almost optimal approximation algorithm for monotone submodular multiple knapsack
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

Cites work

• 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
• All-or-nothing generalized assignment with application to scheduling advertising campaigns
• An approximation algorithm for the generalized assignment problem
• An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Deterministic algorithms for submodular maximization problems
• Deterministic Algorithms for Submodular Maximization Problems
• Generalized assignment of time-sensitive item groups
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Iterative methods in combinatorial optimization.
• Maximizing a monotone submodular function subject to a matroid constraint
• Optimal approximation for the submodular welfare problem in the value oracle model
• Packing groups of items into multiple knapsacks
• Packing items into several bins facilitates approximating the separable assignment problem
• Tight approximation algorithms for maximum separable assignment problems
• Tight Approximation Bounds for the Seminar Assignment Problem

This page was built for publication: Generalized assignment via submodular optimization with reserved capacity

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