𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A performance guarantee for the greedy set-partitioning algorithm

✍ Scribed by E. G. Coffman; M. A. Langston

Publisher
Springer-Verlag
Year
1984
Tongue
English
Weight
355 KB
Volume
21
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The greedy algorithm for partially order
The greedy algorithm for partially ordered sets
✍ Ulrich Faigle πŸ“‚ Article πŸ“… 1979 πŸ› Elsevier Science 🌐 English βš– 756 KB

Those independence systems on finite partially ordered sets are characterized for which the greedy algorithm always works. 'Fhe greedy ulgsrithm far gtartIally ordered fete

A Tight Analysis of the Greedy Algorithm
A Tight Analysis of the Greedy Algorithm for Set Cover
✍ Petr Slavı́k πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 214 KB

We establish significantly improved bounds on the performance of the greedy algorithm for approximating set co¨er. In particular, we provide the first substantial Ž . improvement of the 20-year-old classical harmonic upper bound, H m , of Johnson, Lovasz, and Chvatal, by showing that the performance

Improved performance of the greedy algor
Improved performance of the greedy algorithm for partial cover
✍ Petr SlavΓ­k πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 332 KB

We prove that the classical bounds on the performance of the greedy algorithm for approximating MINIMUM COVER with costs are valid for PARTIAL. COVER as well, thus lowering, by more than a factor of two, the previously known estimate. In order to do so, we introduce a new simple technique that might