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
TitleTight approximation bounds for greedy frugal coverage algorithms
Bibtex cite IDRACTI-RU1-2011-46
Booktitle 5th International Frontiers of Algorithmics Workshop (FAW 11) and the 7th International Conference on Algorithmic Aspects of Information and Management (AAIM 11)
Series LNCS 6681
Year published 2011
Pages 185-195
Publisher Springer
We consider the frugal coverage problem, an interesting vari- ation of set cover deŻned as follows. Instances of the problem consist of a universe of elements and a collection of sets over these elements; the objective is to compute a subcollection of sets so that the number of elements it covers plus the number of sets not chosen is maximized. The problem was introduced and studied by Huang and Svitkina [7] due to its connections to the donation center location problem. We prove that the greedy algorithm has approximation ratio at least 0:782, improving a previous bound of 0:731 in [7]. We also present a further improvement that is obtained by adding a simple corrective phase at the end of the execution of the greedy algorithm. The approximation ratio achieved in this way is at least 0:806. Our analysis is based on the use of linear programs which capture the behavior of the algorithms in worst-case examples. The obtained bounds are proved to be tight.
Caragiannis, Ioannis
Kaklamanis, Christos
Kyropoulou, Maria
FAWAAIM11.pdf (main file)
Publication ID898