Title: An FPTAS for the Knapsack Problem with Parametric Weights,
Abstract: In this paper, we investigate the parametric weight knapsack problem, in
which the item weights are affine functions of the form $w_i(\lambda) = a_i +
\lambda \cdot b_i$ for $i \in \{1,\ldots,n\}$ depending on a real-valued
parameter $\lambda$. 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 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. Our
FPTAS is based on two different approaches and achieves a running time of
$\mathcal{O}(n^3/\varepsilon^2 \cdot \min\{ \log^2 P, n^2 \} \cdot \min\{\log
M, n \log (n/\varepsilon) / \log(n \log (n/\varepsilon) )\})$ where $P$ is an
upper bound on the optimal profit and $M := \max\{W, n \cdot \max\{a_i,b_i: i
\in \{1,\ldots,n\}\}\}$ for a knapsack with capacity $W$.