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.