Computing integral points in convex semi-algebraic sets

被引：11

作者：

Khachiyan, L ^{[1
]}

Porkolab, L ^{[1
]}

机构：

[1] Rutgers State Univ, Dept Comp Sci, New Brunswick, NJ 08903 USA

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646105

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let Y be a convex set in R-k defined by polynomial inequalities and equations of degree at most d greater than or equal to 2 with integer coefficients of binary length l. We show that if Y Omega ZZ(k) not equal 0, then Y contains an integral point of binary length ld(O(k4)). For fixed k, our bound implies a polynomial-time algorithm for computing an integral point y is an element of Y. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming.

引用

页码：162 / 171

页数：10