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
TitleAnalysis of approximation algorithms for k-set cover using factor-revealing linear programs
Bibtex cite IDRACTI-RU1-2007-92
Booktitle 16th International Symposium on Fundamentals of Computation Theory (FCT 2007)
Series LNCS
Year published 2007
Volume 4639
Pages 52-63
Publisher Springer
Note 2007
We present new combinatorial approximation algorithms for k-set cover. Previous approaches are based on extending the greedy al- gorithm by e±ciently handling small sets. The new algorithms further extend them by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the k-set cover problem for all values of k ¸ 6. The analysis technique could be of independent interest; the upper bound on the approximation factor is obtained by bounding the objective value of a factor-revealing linear program.
Athanassopoulos, Stavros
Caragiannis, Ioannis
Kaklamanis, Christos
fct07.pdf (main file)
Publication ID99