Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR14-024 | 19th February 2014 20:32

0-1 Integer Linear Programming with a Linear Number of Constraints

TR14-024
Authors: Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
Publication: 20th February 2014 20:41
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.