We establish significantly improved bounds on the performance of the greedy
algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our
improvements result from a new approach to both problems. In particular,
(a) we improve the known bound on the performance ratio of the greedy
algorithm for general covers without cost, showing that it differs from the classical
harmonic bound by a function which approaches infinity (as the size of the base set
increases);
(b) we show that, for covers without cost, the performance guarantee for the
greedy algorithm is significantly better than the performance guarantee for the
randomized rounding algorithm;
(c) we prove that the classical bounds on the performance of the greedy
algorithm for complete covers with costs are valid for partial covers as well, thus
lowering, by more than a factor of two, the previously known estimate.