An Improved Fptas For 0-1 Knapsack Arxiv
September 6, 2019 - Ce Jin
Print
EmailJournal or Book Title: arXiv
Volume/Issue:
Year Published: 2019
The 0-1 knapsack problem is an important NP-hard problem that admits fully polynomial-time approximation schemes (FPTASs). Previously the fastest FPTAS by Chan (2018) with approximation factor 1 + epsilon runs in O(n + (1/epsilon)12/5) time, where O hides polylogarithmic factors. In this paper we present an improved algorithm in O(n+(1/epsilon)9/4) time, with only a (1/epsilon)1/4gap from the quadratic conditional lower bound based on (min, +)-convolution. Our improvement comes from a multi-level extension of Chans number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items.
Type of Publication: Journal Paper