An analysis of the Greedy Algorithm for Stochastic Set Cover

03/20/2018

∙

by   Srinivasan Parthasarathy, et al.

∙

0

∙

share

We show that the approximation ratio of the greedy algorithm for the stochastic set cover problem is H(m), the m-th Harmonic number, where m is the number of elements in the ground set.