Preserving approximation in the min-weighted set cover problem

DOI10.1016/S0166-218X(96)00047-9MaRDI QIDQ674914zbMATH OpenDBLPWikidataFDO

Authors Giorgio Gambosi, Maurizio Talamo, Marco Protasi

Publication date 30 June 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

Chvatal's algorithmmin-weighted set cover problem

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• On the differential approximation of MIN SET COVER
• SOFSEM 2005: Theory and Practice of Computer Science
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• scientific article; zbMATH DE number 2081030

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)

Cited in

(3)

• Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis
• Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa

This page was built for publication: Preserving approximation in the min-weighted set cover problem

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