A Tight Analysis of the Greedy Algorithm for Set Cover

✍ Scribed by Petr Slavı́k

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 214 KB
• Volume: 25
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0887

✦ Synopsis

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 ratio of the greedy ´´Ž .

algorithm is, in fact, exactly ln m y ln ln m q ⌰ 1 , where m is the size of the ground set. The difference between the upper and lower bounds turns out to be less than 1.1. This provides the first tight analysis of the greedy algorithm, as well Ž . as the first upper bound that lies below H m by a function going to infinity with m. We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on the integrality gap. Our improvements result from a new approach which might be generally useful for attacking other similar problems.