Loading...
Please wait, while we are loading the content...
Similar Documents
Improved performance of the greedy algorithm for the minimum set cover and minimum partial cover problems (1995).
| Content Provider | CiteSeerX |
|---|---|
| Author | Slavík, Petr |
| 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. Keywords: Approximation Algorithms, Combinatorial Optimization, Greedy Algorithm. Department of Mathemati... |
| File Format | |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Greedy Algorithm Minimum Partial Cover Problem Minimum Set Cover Performance Guarantee Combinatorial Optimization Performance Ratio General Cover New Approach Randomized Rounding Algorithm Base Set Increase Minimum Partial Cover Classical Bound Approximation Algorithm Partial Cover Complete Cover Classical Harmonic Bound |
| Content Type | Text |
