A modified greedy algorithm for dispersively weighted 3-set cover

The set cover problem is that of computing a minimum weight subfamily F′F′, given a family FF of weighted subsets of a base set U, such that every element of U   is covered by some subset in F′F′. The k-set cover problem is a variant in which every subset is of size at most k  . It has been long known that the problem can be approximated within a factor of H(k)=∑i=1k(1/i) by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k  -set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of H(3)-1/6H(3)-1/6 can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai–Edmonds structure theorem for maximum matchings.