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 O(n+(1/ε) 2 ) time. This improves upon the O(n+(1/ε) 11/5 )time algorithm by Deng, Jin, and Mao [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/ε) 2-δ )-time FPTAS for any constant δ > 0.