A tight analysis of the greedy algorithm for set cover
Petr Slavı́k · 1996
We establish significantly improved bounds on the performance of the greedy algorithm for approximating set cover.In particular, we provide the first substantial improvement of the 20 year old classical harmonic upper bound, H(m), of Johnson, Lovssz, and ChvAt al, by showing that the performance ratio of the greedy algorithm is, in fact, exactly in m -in ht m + Q(l), 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 ansJysis 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 integralit~gap.Our improvements result from a new approach which might be generally useful for attacking other similar problems.