Approximation of the clustered set covering problem

DOI10.1016/J.ENDM.2010.05.061MaRDI QIDQ2883599zbMATH OpenOpenAlexFDO

Authors Jérôme Monnot, Laurent Alfandari

Publication date 13 May 2012

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2010.05.061

zbMATH Keywords

approximationinteger programmingmaximal coverageNP-hardnessset covering

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• A note on the clustered set covering problem
• Clustering heuristics for set covering
• Approximation of the quadratic set covering problem
• scientific article; zbMATH DE number 2102648
• A fast approximation algorithm for the multicovering problem

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
• Crew pairing at Air France
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Master-slave strategy and polynomial approximation
• Optimization, approximation, and complexity classes
• The budgeted maximum coverage problem

Cited in

(4)

• Multi-dimensional commodity covering for tariff selection in transportation
• Approximation Algorithms for the k-Clique Covering Problem
• A note on the clustered set covering problem
• A Global Constraint for the Exact Cover Problem: Application to Conceptual Clustering

This page was built for publication: Approximation of the clustered set covering problem

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