Type of publication: | Inproceedings |
Entered by: | chita |
Title | Analysis of approximation algorithms for k-set cover using factor-revealing linear programs |
Bibtex cite ID | RACTI-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 |
URL | http://www.conferences.hu/fct2007/ |
Abstract | 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. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments | |
Publication ID | 99 |