Maximum coverage problem with group budget constraints

DOI10.1007/S10878-016-0102-0MaRDI QIDQ1680483zbMATH OpenOpenAlexFDO

Authors Boaz Farbstein, Asaf Levin

Publication date 16 November 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-016-0102-0

zbMATH Keywords

greedy algorithmapproximation algorithmsmaximum coverage

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation algorithms for maximum coverage with group budget constraints
• Efficient approximation algorithms for maximum coverage with group budget constraints
• The budgeted maximum coverage problem
• Improved greedy algorithm for maximum coverage problem with group budget constraints
• The multi-budget maximum weighted coverage problem
• scientific article; zbMATH DE number 6851883
• The generalized maximum coverage problem
• Approximations for restrictions of the budgeted and generalized maximum coverage problems
• The maximin gradual cover location problem

Cites work

• A threshold of ln n for approximating set cover
• Approximation algorithms for NP-hard problems.
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Improved algorithms for orienteering and related problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On the complexity of approximating \(k\)-set packing
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The Maximum Coverage Location Problem
• The budgeted maximum coverage problem

Cited in

(11)

• Maximum coverage with cluster constraints: an LP-based approximation technique
• Approximation algorithms for maximum weighted target cover problem with distance limitations
• Energy-constrained geometric coverage problem
• A 1/2 approximation algorithm for energy-constrained geometric coverage problem
• scientific article; zbMATH DE number 6851883 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Graph burning in community-based networks
• Approximation algorithms for maximum coverage with group budget constraints
• Improved greedy algorithm for maximum coverage problem with group budget constraints
• Efficient approximation algorithms for maximum coverage with group budget constraints
• The multi-budget maximum weighted coverage problem

This page was built for publication: Maximum coverage problem with group budget constraints

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