Center for Algorithms and Theory of Computation

CS 269S, Winter 2018: Theory Seminar
Bren Hall, Room 1423, 1pm

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.)