Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the

number of variables and $cn$ is the number of constraints. The key ...
more >>>