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 harder to approximate than a less general class of modular incremental knapsack problems, that have been investigated in the literature. We also show that certain extensions to more general submodular functions are APX-hard.
The Incremental Knapsack Problem with Monotone Submodular All-or-Nothing Profits / D'Onofrio, Federico; Faenza, Yuri; Zhang, Lingyi. - (2023).
The Incremental Knapsack Problem with Monotone Submodular All-or-Nothing Profits
Federico D'Onofrio
;Yuri Faenza
;
2023
Abstract
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 harder to approximate than a less general class of modular incremental knapsack problems, that have been investigated in the literature. We also show that certain extensions to more general submodular functions are APX-hard.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
