# Lipton, Dick

## Exponential Algorithms for Knapsack ★★

Author(s): Lipton

**Conjecture**

The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?

Keywords: Algorithm construction; Exponential-time algorithm; Knapsack