research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleA 6/5-approximation algorithm for the maximum 3-cover problem
Bibtex cite IDRACTI-RU1-2008-59
Booktitle 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008)
Series LNCS 5162
Year published 2008
Pages 205-216
In the maximum cover problem, we are given a collection of sets over a ground set of elements and a positive integer w, and we are asked to compute a collection of at most w sets whose union contains the maximum number of elements from the ground set. This is a fundamental combinatorial optimization problem with applications to resource allo- cation. We study the simplest APX-hard variant of the problem where all sets are of size at most 3 and we present a 6=5-approximation algo- rithm, improving the previously best known approximation guarantee. Our algorithm is based on the idea of ¯rst computing a large packing of disjoint sets of size 3 and then augmenting it by performing simple local improvements.
Caragiannis, Ioannis
Monaco, G.
mfcs08.pdf (main file)
Publication ID521