120 citations · 268 across the 16 of their papers we have counts for
4 papers · 1 filter
Inclusion-wise extremal knapsack problems are (mostly) hard to approximate
Fabio Ciccarelli, Fabio Furini, Ulrich Pferschy +1
We study two inclusion-wise extremal variants of the 0-1 Knapsack Problem (KP). Given items with integer weights and nonnegative costs or profits, the Minimum-Cost Maximal Knap…
Optimally rescheduling jobs with a LIFO buffer
Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy +2
This paper considers single-machine scheduling problems in which a given solution, i.e. an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. Th…
Approximating the Incremental Knapsack Problem
Federico Della Croce, Ulrich Pferschy, Rosario Scatamacchia
We consider the 0-1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed…
Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem
Federico Della Croce, Ulrich Pferschy, Rosario Scatamacchia
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 v…