Point Containment in the Integer Hull of a Polyhedron

Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn

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^2 \log m)$ in any fixed dimension. This improves on the algorithm which is based on the equivalence of separation and optimization and on a direct algorithm (SODA 97) for the two-dimensional case.

Proc. of 15th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, New Orleans