A Modified Greedy Algorithm for the Set Cover Prob

Authors: Toshihiro Fujito Tsuyoshi Okumura

Publish Date: 2001/12/19

Volume: , Issue: , Pages: 670-681

PDF Link

Abstract

The set cover problem is that of computing given a family of weighted subsets of a base set U a minimum weight subfamily F′ such that every element of U is covered by some subset in F′ The kset cover problem is a variant in which every subset is of size bounded by k It has been long known that the problem can be approximated within a factor of Hleft k right = sumnolimits i = 1k left 1 mathordleft/ vphantom 1 i right kernnulldelimiterspace i right 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 kset cover problem as a first step towards better approximation of general k set cover problem where subset costs are limited to either 1 or 2 It will be shown via LP duality that improved approximation bounds of H31/6 for 3set cover and Hk1/12 for kset cover can be attained when the greedy heuristic is suitably modified for this case

Keywords: