Approximation schemes for the parametric knapsack problem

Alberto Giudici, Pascal Halffmann, Stefan Ruzika, Clemens Thielen

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


We consider the (linear) parametric 0–1 knapsack problem in which the profits of the items are affine-linear functions of a real-valued parameter and the task is to compute a solution for all values of the parameter. For this problem, it is known that the piecewise linear convex function mapping the parameter to the optimal objective value of the corresponding instance (called the optimal value function) can have exponentially many breakpoints (points of slope change), which implies that every optimal algorithm for the problem must output a number of solutions that is exponential in the number of items. We provide the first (parametric) polynomial time approximation scheme (PTAS) for the parametric 0–1 knapsack problem. Moreover, we exploit the connection between the parametric problem and the bicriteria problem in order to show that the parametric 0–1 knapsack problem admits a parametric FPTAS when the parameter is restricted to the positive real line and the slopes and intercepts of the affine-linear profit functions of the items are nonnegative. The method used to obtain this result applies to many linear parametric optimization problems and provides a general connection between bicriteria and linear parametric optimization problems.

Original languageEnglish
Pages (from-to)11-15
Number of pages5
JournalInformation Processing Letters
StatePublished - 1 Apr 2017
Externally publishedYes


  • Approximation algorithms
  • Bicriteria optimization problems
  • Parametric optimization problems


Dive into the research topics of 'Approximation schemes for the parametric knapsack problem'. Together they form a unique fingerprint.

Cite this