New performance guarantees for the greedy maximization of submodular set functions

Jussi Laitila, Atte Moilanen

We present new tight performance guarantees for the greedy maximization of nondecreasing submodular set functions. Our main result first provides a performance guarantee in terms o…