On integer points in polyhedra (Q1193530): Difference between revisions

Consider an \(n\)-dimensional polyhedron \(P\) determined by \(m\) inequalities of size \(\phi\). The integer hull \(P_ I\) of \(P\) is the convex hull of all integer points lying in \(P\). The study on the integer hull is related to the integer programming. In this paper, the authors prove that the number of vertices of \(P_ I\) is at most \(O(m^ n\phi^{n-1})\). They also present an approximation algorithm which can determine the number of integer points in \(P\) within a factor of \(1+\varepsilon\) in time polynomial in \(m\), \(\phi\), and \(1/\varepsilon\) when the dimension \(n\) is fixed.