We consider the 0–1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an ILP solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases which still permit fully polynomial time approximation schemes (FPTASs) and others where the problem remains hard to approximate.

Improved dynamic programming and approximation results for the knapsack problem with setups / Pferschy, Ulrich; Scatamacchia, Rosario. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 25:(2018), pp. 667-682. [10.1111/itor.12381]

Improved dynamic programming and approximation results for the knapsack problem with setups

SCATAMACCHIA, ROSARIO
2018

Abstract

We consider the 0–1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an ILP solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases which still permit fully polynomial time approximation schemes (FPTASs) and others where the problem remains hard to approximate.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2656753
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo