A Faster FPTAS for the Unbounded Knapsack Problem

Abstract

The Unbounded Knapsack Problem (UKP) is a well-known variant of the famous 0-1 Knapsack Problem (0-1 KP). In contrast to 0-1 KP, an arbitrary number of copies of every item can be taken in UKP. Since UKP is NP-hard, fully polynomial time approximation schemes (FPTAS) are of great interest. Such algorithms find a solution arbitrarily close to the optimum $\mathrm{OPT}(I)$, i.e. of value at least $(1-\epsilon )\mathrm{OPT}(I)$ for $\epsilon >0$, and have a running time polynomial in the input length and $\frac{1}{\epsilon }$. For over thirty years, the best FPTAS was due to Lawler with a running time in $O(n+\frac{1}{{\epsilon }^3})$ and a space complexity in $O(n+\frac{1}{{\epsilon }^2})$, where $n$ is the number of knapsack items. We present an improved FPTAS with a running time in $O(n+\frac{1}{{\epsilon }^2}{\log }^3\frac{1}{\epsilon })$ and a space bound in $O(n+\frac{1}{\epsilon }{\log }^2\frac{1}{\epsilon })$. This directly improves the running time of the fastest known approximation schemes for Bin Packing and Strip Packing, which have to approximately solve UKP instances as subproblems.

30 pages, pdfLaTeX; typos corrected, additional smaller explanations to improve readability and to avoid confusion; full version of paper presented at IWOCA 2015, reviewer comments were taken into account