penalized knapsack problem

Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem

  • Federico Della Croce
  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , ,

    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 … Read more