A Nearly Quadratic-Time FPTAS for Knapsack

We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in $\tilde{O}(n+(1\mathrm{/}\epsilon {)}^2)$ time. This improves upon the $\tilde{O}(n+(1\mathrm{/}\epsilon {)}^{11\mathrm{/}5})$-time algorithm by Deng, Jin, and Mao [$\mathit{\text{Proceedings}}\mathit{\text{of}}\mathit{\text{the}}\mathit{\text{2023}}\mathit{\text{Annual}}\mathit{\text{ACM-SIAM}}\mathit{\text{Symposium}}\mathit{\text{on}}\mathit{\text{Discrete}}\mathit{\text{Algorithms,}}\mathit{\text{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\mathrm{/}\epsilon {)}^{2-\delta })$-time FPTAS for any constant $\delta >0$.