Title: An FPTAS for the parametric knapsack problem,
Abstract: In this paper, we investigate the parametric knapsack problem, in which the
item profits are affine functions 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 a fully polynomial-time approximation scheme
(FPTAS) for the problem that, for any desired precision $\varepsilon \in
(0,1)$, computes $(1-\varepsilon)$-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
$\mathcal{O}(\frac{n^2}{\varepsilon})$ knapsack solutions and runs in strongly
polynomial-time $\mathcal{O}(\frac{n^4}{\varepsilon^2})$. Even for the special
case of positive input data, this is the first FPTAS with a strongly polynomial
running time. We also show that this time bound can be further improved to
$\mathcal{O}(\frac{n^2}{\varepsilon} \cdot A(n,\varepsilon))$, where
$A(n,\varepsilon)$ denotes the running time of any FPTAS for the traditional
(non-parametric) knapsack problem.