ECCC-Report TR14-024https://eccc.weizmann.ac.il/report/2014/024Comments and Revisions published for TR14-024en-usThu, 20 Feb 2014 20:41:36 +0200
Paper TR14-024
| 0-1 Integer Linear Programming with a Linear Number of Constraints |
Stefan Schneider,
Russell Impagliazzo,
Shachar Lovett,
Ramamohan Paturi
https://eccc.weizmann.ac.il/report/2014/024We 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.
Thu, 20 Feb 2014 20:41:36 +0200https://eccc.weizmann.ac.il/report/2014/024