The Incremental Knapsack Problem with Monotone Submodular All-or-Nothing Profits

Federico D'Onofrio, Yuri Faenza, Lingyi Zhang

We study incremental knapsack problems with profits given by a special class of monotone submodular functions, that we dub all-or-nothing. We show that these problems are not harde…