Approximating k-Set Cover and Complementary Graph Coloring

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

We consider instances of the Set Cover problem where each set is of small size. For collections of sets of size at most three, we obtain improved performance ratios of 1.4 + eps, for any constant eps > 0. Similar improvements hold also for collections of larger sets. A corollary of this result is an improved performance ratio of 4/3 for the problem of minimizing the unused colors in a graph coloring.