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,\dots ,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 $\epsilon \in (0,1)$, computes $(1-\epsilon )$-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/{\epsilon }^2\cdot \min \{{\log }^{2}P,n^2\}\cdot \min \{\log M,n\log (n/\epsilon )/\log (n\log (n/\epsilon ))\})$ where $P$ is an upper bound on the optimal profit and $M:=\max \{W,n\cdot \max \{a_i,b_i:i\in \{1,\dots ,n\}\}\}$ for a knapsack with capacity $W$.

arXiv admin note: text overlap with arXiv:1701.07822

References in corpus (1)

• An FPTAS for the parametric knapsack problem