A Nearly Quadratic-Time FPTAS for Knapsack

08/15/2023
by   Lin Chen, et al.
0

We investigate polynomial-time approximation schemes for the classic 0-1 knapsack problem. The previous algorithm by Deng, Jin, and Mao (SODA'23) has approximation factor 1 + with running time O(n + 1/^2.2). There is a lower Bound of (n + 1/)^2-o(1) conditioned on the hypothesis that (min, +) has no truly subquadratic algorithm. We close the gap by proposing an approximation scheme that runs in O(n + 1/^2) time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset