An FPTAS for the knapsack problem with parametric weights

In this paper, we investigate the parametric weight knapsack problem, in which the item weights are affine functions of the form  wi(λ)=ai+λ⋅bi for i∈{1,…,n} depending on a real-valued parameter λ. The aim is to provide a solution for all values of the parameter. It is well-known that any exact algorithm for the problem may need to output an exponential number of knapsack solutions. We present the first fully polynomial-time approximation schemes (FPTASs) for the problem that, for any desired precision ε∈(0,1), compute (1−ε)-approximate solutions for all values of the parameter. Among others, we present a strongly polynomial FPTAS running in On5ε2⋅log3nεlogn time and a weakly polynomial FPTAS with a running time of On3ε2⋅log2nε⋅logP⋅logMlogn, where P is an upper bound on the optimal profit and M≔max{|W|,n⋅max{|ai|,|bi|:i∈{1,…,n}}} for a knapsack with capacity W.