Greedy differential approximations for Min Set Cover

DOI10.1007/978-3-540-30577-4_9MaRDI QIDQ5711562zbMATH OpenOpenAlexFDO

Authors Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serriére, Cristina Bazgan

Publication date 7 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b105088

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• On the differential approximation of MIN SET COVER
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Differential approximation algorithms for some combinatorial optimization problems
• A modified greedy algorithm for the set cover problem with weights 1 and 2

Cited in

(7)

• On the differential approximation of MIN SET COVER
• Greedy approximations for minimum submodular cover with submodular cost
• New and improved bounds for the minimum set cover problem
• Approximating min-sum set cover
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• Preserving approximation in the min-weighted set cover problem

This page was built for publication: Greedy differential approximations for Min Set Cover

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