Lipton, Dick

Exponential Algorithms for Knapsack ★★

Author(s): Lipton

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{1},x_{2},\dots,x_{n}$ so that $$ \sum_{i=1}^{n} a_{i}x_{i} = b.$$ The best known worst-case algorithm runs in time $2^{n/2}$ times a polynomial in $n$. Is there an algorithm that runs in time $2^{n/3}$?


Keywords: Algorithm construction; Exponential-time algorithm; Knapsack

Syndicate content