The set cover problem is an optimization problem that models many resource selection problems. Given a base set U and a family of weighted subsets of U, the problem is to find a minimum weight subfamily such that each element of U belongs to at least one subset in the subfamily. The k-set cover problem is its variant where each subset is of size at most k. The greedy algorithm is known to yield a performance ratio of H(k) = ∑{sub}(i=1){sup}k(1/i), but no better bound is shown except for the case of unweight subsets. In this paper we consider the 3-set cover problem where subset weights are restricted to 1 and some constant d. For the case of d ≥ 2 the approximation bound of H(3) - 1/6 was previously obtained. So we consider the case of 1.5 ≤ d ≤ 3, and show how to modify the greedy algorithm, using the LP duality, so as to yield the same approximation bound.
展开▼
