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]
|Titolo:||Improved dynamic programming and approximation results for the knapsack problem with setups|
|Data di pubblicazione:||2018|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1111/itor.12381|
|Appare nelle tipologie:||1.1 Articolo in rivista|
File in questo prodotto: