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