The multi-budget maximum weighted coverage problem

DOI10.1007/978-3-030-75242-2_12MaRDI QIDQ2692723

Gianpiero Monaco, Yllka Velaj, Francesco Cellinese, Gianlorenzo D'Angelo

Publication date: 22 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_12

zbMATH Keywords

approximation algorithms; maximum coverage; multi-budget coverage

Mathematics Subject Classification ID

68Wxx: Algorithms in computer science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generalized maximum coverage problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Maximum coverage problem with group budget constraints
• A 6/5-approximation algorithm for the maximum 3-cover problem
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Submodular Function Minimization under Covering Constraints
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Distributed Welfare Games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties