An Improved FPTAS for 0-1 Knapsack

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/4} gap from the quadratic conditional lower bound based on (min,+)-convolution. Our improvement comes from a multi-level extension of Chan\u27s number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items