Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Petr Slavik:

TR95-053 | 15th October 1995
Petr Slavik

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

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 ... more >>>

ISSN 1433-8092 | Imprint