Abstract.
Let Y be a convex set in \Re k defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min \(\{ y_k \mid y=(y_1, . . . ,y_k) \in Y \cap \Ze^k \}\) is not empty, then the problem has an optimal solution \(y^* \in Y \cap \Ze^k\) of binary length ld O(k4) . For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y * . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received August 3, 1998, and in revised form March 22, 1999.
Rights and permissions
About this article
Cite this article
Khachiyan, L., Porkolab, L. Integer Optimization on Convex Semialgebraic Sets . Discrete Comput Geom 23, 207–224 (2000). https://doi.org/10.1007/PL00009496
Issue Date:
DOI: https://doi.org/10.1007/PL00009496