97-14: Computing Integral Points in Convex Semi-algebraic Sets

DIMACS TR: 97-14

Computing Integral Points in Convex Semi-algebraic Sets

Authors: Leonid Khachiyan and Lorant Porkolab

ABSTRACT
Let $Y$ be a convex set in $R^k$ defined by polynomial inequalities and equations of degree $d \ge 2$ with integer coefficients of binary length $l$. We show that if $Y \cap Z^k \ne \emptyset$, then $Y$ contains an integral point of binary length $ld^{O(k^4)}$. For fixed $k$, our bound implies a polynomial-time algorithm for computing an integral point $y \in Y$. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-14.ps.gz

DIMACS Home Page