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):|
|Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView|