Paper Info
Title
Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem.
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
Venue
Field
2017
arXiv: Data Structures and Algorithms
Dynamic programming,Mathematical optimization,Combinatorics,Exact algorithm,Algorithm,Continuous knapsack problem,Solver,Knapsack problem,Time complexity,Linear programming relaxation,Mathematics
DocType
Volume
Citations 
Journal
abs/1702.04211
2
PageRank 
References 
Authors
0.44
3
3
Name
Order
Citations
PageRank
Federico Della Croce139941.60
Ulrich Pferschy287583.57
Rosario Scatamacchia3587.66