An Improved FPTAS for 0-1 Knapsack

Abstract

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 $\tilde{O}(n+(1/\epsilon {)}^{12/5})$ time, where $\tilde{O}$ hides polylogarithmic factors. In this paper we present an improved algorithm in $\tilde{O}(n+(1/\epsilon {)}^{9/4})$ time, with only a $(1/\epsilon {)}^{1/4}$ gap from the quadratic conditional lower bound based on $(\min ,+)$-convolution. Our improvement comes from a multi-level extension of Chan's number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items.

To appear at ICALP'19