Browsing by Subject "Approximation"

Sort by: Order: Results:

Now showing items 1-1 of 1
  • Laitila, Jussi; Moilanen, Atte (2017)
    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.