A Nearly Quadratic-Time FPTAS for Knapsack

Lin Chen, Jiayi Lian, Yuchen Mao +1

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…