Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints

DOI10.1287/moor.2013.0592zbMath1291.90205arXiv1101.2940OpenAlexW2109309418MaRDI QIDQ5169688

Ariel Kulik, Tami Tamir, Hadas Shachnai

Publication date: 11 July 2014

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

generalized assignment problemrandomizationapproximation algorithmsknapsack constraintssubmodular maximizationmaximum coverage

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (29)

Streaming Algorithms for Submodular Function Maximization ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Constrained Assortment Optimization Under the Paired Combinatorial Logit Model ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ Optimization with demand oracles ⋮ The knapsack problem with neighbour constraints ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems ⋮ The multi-budget maximum weighted coverage problem ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Practical budgeted submodular maximization ⋮ Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Discrete optimization methods for group model selection in compressed sensing ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Unnamed Item ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ Tight Approximation for Unconstrained XOS Maximization ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints