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 F F 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 = 1 k ( 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/6 H ( 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 GallaiEdmonds structure theorem for maximum matchings.
greedy algorithm set cover approximation algorithms primaldual method