Approximation schemes for the parametric knapsack problem

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.