## January 26, 2018:

# Approximation Schemes for 0-1 Knapsack

## Pedro Matias

We revisit the standard 0-1 knapsack problem. The latest
polynomial-time approximation scheme by Rhee (2015) with approximation
factor $1+\epsilon$ has running time near $\displaystyle\tilde{O}\bigl(n +
\epsilon^{-5/2}\bigr)$ (ignoring polylogarithmic factors), and is
randomized. We present a simpler algorithm which achieves the same
result and is deterministic. With more effort, our ideas can actually
lead to an improved time bound near
$\displaystyle\tilde{O}\bigl(n +
\epsilon^{-12/5}\bigr)$, and still further
improvements for small $n$.

(Based on a
paper by Timothy Chan
from SOSA 2018.)