Bounds on the Performance of a Greedy Algorithm for Probabilities

A bound on the performance of the greedy algorithm for finding the maximum of a submodular set function subject to a cardinality constraint is shown to apply to the problem of selecting a fixed number of events so that the probability that at least one of the selected events occurs is maximized. The bound is improved under an additional assumption which is plausible when the aim is to find a biologically active compound in pharmaceutical research.