Integer Optimization on Convex Semialgebraic Sets |
| |
Authors: | L Khachiyan L Porkolab |
| |
Institution: | (1) Department of Computer Science, Rutgers University, New Brunswick, NJ 08903, USA leonid@cs.rutgers.edu, US;(2) Max Planck Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany porkolab@data.mpi-sb.mpg.de, DE |
| |
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 is not empty, then the problem has an optimal solution 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.
Received August 3, 1998, and in revised form March 22, 1999. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|