TY - JOUR
TI - Computing Integral Points In Convex Semi-algebraic Sets
DO - https://doi.org/doi:10.7282/T3765JV2
AU - Khachiyan, Leonid
AU - Porkolab, Lorant
PY - 1996
AB - Let Y be a convex set in IR^k defined by polynomial inequalities and equations of degree at most d>=2 with integer coefficients of binary length l. We show that if Y(intersection)Z^k != 0, then Y contains an integral point of binary length ld^0(k^4). For fixed k, our bound implies a polynomial-time algorithm for computing an integral point y E Y . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming.
LA - English
ER -