Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | DocType |
|---|---|---|
2014 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
abs/1401.5512 | 13 | 0.76 |
References | Authors | |
3 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Shachar Lovett | 2 | 520 | 55.02 |
| Ramamohan Paturi | 3 | 1260 | 92.20 |
| Stefan Schneider | 4 | 56 | 3.07 |