PORTO @ 
Archivio Istituzionale della Ricerca
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range of penalties, on the identification of a core problem and on dynamic programming. The proposed approach turns out to be very effective in solving hard instances of PKP and compares favorably both to commercial solver CPLEX 12.5 applied to the ILP formulation of the problem and to the best available exact algorithm in the literature. Then we present a general inapproximability result and investigate several relevant special cases which permit fully polynomial time approximation schemes (FPTASs).
New exact approaches and approximation results for the Penalized Knapsack Problem / Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 253(2019), pp. 122-135. [10.1016/j.dam.2017.11.023]
| Titolo: | New exact approaches and approximation results for the Penalized Knapsack Problem | |
| Autori: | ||
| Data di pubblicazione: | 2019 | |
| Rivista: | ||
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.dam.2017.11.023 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11583/2698735
Copyright © 2022