ALCOMFT-TR-03-184

Ernst Althaus, Fritz Eisenbrand, Stefan Funke and Kurt Mehlhorn
Point Containment in the Integer Hull of a Polyhedron
MPI. Work package 4. December 2003.

Abstract: We show that the point containment problem in the integer hull of a polyhedron, which is defined by m inequalities, with coefficients of at most \varphi bits can be solved in time \bigO(m+\varphi) in the two-dimensional case and in expected time \bigO(m+\varphi² log m) in any fixed dimension. This improves on the algorithm which is based on the equivalence of separation and optimization in the general case and on a direct algorithm (SODA 97) for the two-dimensional case.

Postscript file: ALCOMFT-TR-03-184.ps.gz (196 kb).