0-1 Integer Linear Programming with a Linear Number of Constraints
Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Previously Published Works bannerUC San Diego

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

  • Author(s): Impagliazzo, Russell
  • Lovett, Shachar
  • Paturi, Ramamohan
  • Schneider, Stefan
  • et al.

Published Web Location

https://arxiv.org/abs/1401.5512
No data is associated with this publication.
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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item