Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VECTOR DOMINATION:
Reports tagged with Vector Domination:
TR14-024 | 19th February 2014
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

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

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 >>>




ISSN 1433-8092 | Imprint