𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A disturbed version of the greedy algorithm

✍ Scribed by W. Wenzel

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
147 KB
Volume
12
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

We study a disturbed variant of the classical greedy algorithm for weight functions defined on some given finite set E and show that the greedy algorithm for matroids is stable with respect to changes in the input data.

πŸ“œ SIMILAR VOLUMES

A faster version of the ASG algorithm
A faster version of the ASG algorithm
✍ N.L. Boland; A.T. Ernst; C.J. Goh; A.I. Mees πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 300 KB
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