Integer polynomial optimization in fixed dimension

Integer polynomial optimization in fixed dimension

0.00 Avg rating0 Votes
Article ID: iaor200928634
Country: United States
Volume: 31
Issue: 1
Start Page Number: 147
End Page Number: 153
Publication Date: Feb 2006
Journal: Mathematics of Operations Research
Authors: , , ,
Abstract:

We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients, and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are nonnegative over the polytope, these sequences of bounds lead to a fully polynomial–time approximation scheme for the optimization problem.

Reviews

Required fields are marked *. Your email address will not be published.