A faster FPTAS for the Unbounded Knapsack Problem.

Jansen, Klaus and Kraft, Stefan E.J. (2018) A faster FPTAS for the Unbounded Knapsack Problem. European Journal of Combinatorics, 68 . pp. 148-174. DOI 10.1016/j.ejc.2017.07.016.

Full text not available from this repository.

Supplementary data:

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 OPT(I), i.e., of value at least (1-ε)OPT(I) for ε>0, and have a running time polynomial in the input length and 1ε. For over thirty years, the best FPTAS was due to Lawler with running time O(n+1ε3) and space complexity O(n+1ε2), where n is the number of knapsack items. We present an improved FPTAS with running time O(n+1ε2log31ε) and space bound O(n+1εlog21ε). 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.

Document Type: Article
Research affiliation: Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence
Kiel University
Refereed: Yes
Open Access Journal?: No
DOI etc.: 10.1016/j.ejc.2017.07.016
ISSN: 0195-6698
Projects: Future Ocean
Date Deposited: 19 Dec 2017 10:22
Last Modified: 14 Mar 2019 10:24
URI: http://oceanrep.geomar.de/id/eprint/40868

Actions (login required)

View Item View Item