Name
Abstract | ||
|---|---|---|
We 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). |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2017.11.023 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Penalized Knapsack Problem,Exact algorithm,Dynamic programming,Approximation schemes | Dynamic programming,Discrete mathematics,Mathematical optimization,Exact algorithm,Solver,Knapsack problem,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
253 | 0166-218X | 2 |
PageRank | References | Authors |
0.40 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Federico Della Croce | 1 | 399 | 41.60 |
| Ulrich Pferschy | 2 | 875 | 83.57 |
| Rosario Scatamacchia | 3 | 58 | 7.66 |