Datensatz

Zusammenfassung

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 $O(m+\varphi)$ in the two-dimensional case and in expected time $O(m+\varphi^2 \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.