Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Fast integer programming in fixed dimension

Eisenbrand, Friedrich

MPI-I-2003-NWG2-002. March 2003, 14 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Dimension with a fixed
number of constraints can be computed with $O(s)$ basic
arithmetic operations, where $s$ is the binary
encoding length of the input.
This improves on the quadratic running time of
previous algorithms, which are based on Lenstra's algorithm
and binary search.

It follows that an integer program in fixed dimension, which is
defined by $m$ constraints, each of binary encoding length at most
$s$, can be solved with an expected number of $O(m + \log m \, s)$
arithmetic operations using Clarkson's random sampling algorithm.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2003-NWG2-002.ps143 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Eisenbrand, Friedrich},
  TITLE = {Fast integer programming in fixed dimension},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-NWG2-002},
  MONTH = {March},
  YEAR = {2003},
  ISSN = {0946-011X},