Maximum coverage with cluster constraints: an LP-based approximation technique

DOI10.1007/978-3-030-80879-2_5MaRDI QIDQ2117688zbMATH OpenOpenAlexFDO

Authors Guido Schäfer, Bernard G. Zweers

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/2012.04420, https://ir.cwi.nl/pub/31402

zbMATH Keywords

budgeted maximum coverage problemiterative roundingmultiple knapsack problempipage rounding

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites work

• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• 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
• An analysis of approximations for maximizing submodular set functions—I
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for a two-phase knapsack problem
• Approximation schemes for knapsack problems with shelf divisions
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Efficient approximation algorithms for maximum coverage with group budget constraints
• Exact methods for the knapsack problem and its generalizations
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximum coverage problem with group budget constraints
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• The budgeted maximum coverage problem

Cited in

(2)

• A Global Constraint for the Exact Cover Problem: Application to Conceptual Clustering
• Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique

This page was built for publication: Maximum coverage with cluster constraints: an LP-based approximation technique

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