APPROXIMATE SET COVERING IN UNIFORM HYPERGRAPHS

The weighted set covering problem, restricted to the class of r-unifor m hypergraphs, is considered. We propose a new approach, based on a re cent result of Aharoni, Holzman. and Krivelevich about the ratio of in teger and fractional covering numbers in k-colorable r-uniform hypergr aphs. This approach, applied to hypergraphs of maximal degree bounded by Delta, yields an algorithm with approximation ratio r(1 - c/Delta(1 /(r-1))). Next, we combine this approach with an adaptation of the loc al ratio theorem of Bar-Yehuda and Even for hypergraphs and present a general framework of approximation algorithms, based on subhypergraph exclusion. An application of this scheme is described, providing an al gorithm with approximation ratio r(1-c/n((r-1)/r)) for hypergraphs on n vertices. We discuss also the limitations of this approach. (C) 1997 Academic Press.