An FPTAS for the parametric knapsack problem

We present a fully polynomial-time approximation scheme (FPTAS) for the problem that, for any desired precision ε∈(0,1), computes (1−ε)-approximate solutions for all values of the parameter. This is the first FPTAS for the parametric knapsack problem that does not require the slopes and intercepts of the affine functions to be non-negative but works for arbitrary integral values. Our FPTAS outputs O(n2ε) knapsack solutions and runs in strongly polynomial-time O(n2ε⋅A(n,ε)), where A(n,ε) denotes the running time of any FPTAS for the traditional (non-parametric) knapsack problem. Even for the special case of positive input data, this is the first FPTAS with a strongly polynomial running time.