MPI-I-2003-NWG2-002
Fast integer programming in fixed dimension
Eisenbrand, Friedrich
March 2003, 14 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2003-NWG2-002.ps (143 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-NWG2-002
BibTeX
@TECHREPORT{Eisenbrand2003,
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},
}