We present new tight performance guarantees for the greedy maximization of monotone submodular set functions. Our main result first provides a performance guarantee in terms of the overlap of the optimal and greedy solutions. As a consequence we improve performance guarantees of Nemhauser et al. (Math Program 14:265–294, 1978) and Conforti and Cornuejols (Discr Appl Math 7:251–274, 1984) for maximization over subsets, which are at least half the size of the problem domain. As a further application, we obtain a new tight approximation guarantee in terms of the cardinality of the problem domain.
['Jussi Laitila', 'Atte Moilanen']
New performance guarantees for the greedy maximization of submodular set functions