A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
Refael Hassin, Asaf Levin · SIAM Journal on Computing · 2005
In the weighted set-cover problem we are given a set of elements $E=\{ e_1,e_2, \ldots ,e_n \}$ and a collection $\cal F$ of subsets of E, where each $S \in \cal F$ has a positive cost $c_{S}$. The problem is to compute a subcollection $SOL$ such that $\bigcup_{S\in SOL}S_j=E$ and its cost $\sum_{S\in SOL}c_S$ is minimized. When $|S|\le k\ \forall S\in\cal F$ we obtain the weighted k-set cover problem. It is well known that the greedy algorithm is an $H_k$-approximation algorithm for the weighted k set cover, where $H_k=\sum_{i=1}^k {1 \over i}$ is the kth harmonic number, and that this bound is exact for the greedy algorithm for all constant values of k. In this paper we give the first improvement on this approximation ratio for all constant values of k. This result shows that the greedy algorithm is not the best possible for approximating the weighted set cover problem. Our method is a modification of the greedy algorithm that allows the algorithm to regret.