Efficient approximation algorithms for maximum coverage with group budget constraints

DOI10.1016/j.tcs.2019.02.015zbMath1423.68591OpenAlexW2917019893MaRDI QIDQ2317355

Min Li, Longkun Guo, Da-Chuan Xu

Publication date: 9 August 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.02.015

zbMATH Keywords

approximation algorithmnetwork flowauxiliary graphmaximum coverage problem with group budget constraintsrandomized linear programming rounding

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum coverage problem with group budget constraints
• A threshold of ln n for approximating set cover
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Fast algorithms for maximizing submodular functions
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Efficient approximation algorithms for maximum coverage with group budget constraints