Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-053 | 15th October 1995 00:00

Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems

RSS-Feed




TR95-053
Authors: Petr Slavik
Publication: 31st October 1995 20:00
Downloads: 1367
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint