Integer optimization on convex semialgebraic sets
type: Item
instance of: scholarly article
title: Integer optimization on convex semialgebraic sets
zbMATH Open document ID: 0966.90059
DOI: 10.1007/PL00009496
published in: Discrete \& Computational Geometry
publication date: 2000-03-23T00:00:00Z
review text: Let \(Y\) be a convex set in \(\mathbb{R}^k\) defined by polynomial inequalities and equations of degree at most \(d\geq 2\) with integer coefficients of binary length at most \(\ell\). The main result states that if the set of optimal solutions of the integer programming problem \(\min\{y_k\mid y=(y_1, \dots, y_k)\in Y\cap \mathbb{Z}^k\}\) is not empty, then the problem has an optimal solution \(y^*\in Y\cap \mathbb{Z}^k\) of binary length \(\ell d^{O(k4)}\). Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension is extended to semidefinite integer programming.
reviewed by: V.Peteanu
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 1422799
zbMATH Keywords: convex semialgebraic sets
zbMATH Keywords: semidefinite integer programming
author: Leonid G. Khachiyan
author: Lorant Porkolab
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1422799