A Nearly Quadratic-Time FPTAS for Knapsack

Abstract

We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in $\tilde{O}(n+(1/\epsilon {)}^2)$ time. This improves upon the $\tilde{O}(n+(1/\epsilon {)}^{11/5})$-time algorithm by Deng, Jin, and Mao [\textit{Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, 2023}]. Our algorithm is the best possible (up to a polylogarithmic factor) conditioned on the conjecture that $(\min ,+)$-convolution has no truly subquadratic-time algorithm, since this conjecture implies that Knapsack has no $O((n+1/\epsilon {)}^{2-\delta })$-time FPTAS for any constant $\delta >0$.