✦ LIBER ✦

The greedy coloring is a bad probabilistic algorithm

✍ Scribed by Luděk Kučera

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 505 KB
Volume: 12
Category: Article
ISSN: 0196-6774
DOI: 10.1016/0196-6774(91)90040-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The greedy algorithm is optimal for on-l

The greedy algorithm is optimal for on-line edge coloring

✍ Amotz Bar-Noy; Rajeev Motwani; Joseph Naor 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 270 KB

A disturbed version of the greedy algori

A disturbed version of the greedy algorithm

✍ W. Wenzel 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

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.

Valuated matroids: a new look at the gre

Valuated matroids: a new look at the greedy algorithm

✍ Andreas W.M. Dress; Walter Wenzel 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 212 KB

A performance guarantee for the greedy s

A performance guarantee for the greedy set-partitioning algorithm

✍ E. G. Coffman; M. A. Langston 📂 Article 📅 1984 🏛 Springer-Verlag 🌐 English ⚖ 355 KB

Note: On the greedy algorithm for optima

Note: On the greedy algorithm for optimal assembly

✍ Laurence A. Baxter; Farid Harche 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 2 views

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