TR14-024 Authors: Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

Publication: 20th February 2014 20:41

Downloads: 13674

Keywords:

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 idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.