Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs

We present new combinatorial approximation algorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend these approaches 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 ka parts per thousand yen6. The analysis technique used 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.