hide
Free keywords:
-
Abstract:
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.
