Integer polynomial optimization in fixed dimension

• 成果类型: Article
• 署名作者: De Loera, JA; Hemmecke, R; Köppe, M; Weismantel, R
• 署名单位: University of California System; University of California Davis; Otto von Guericke University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0169
• 发表日期: 2006
• 页码: 147-153
• 关键词: algorithm

摘要

We classify according to their computational complexity, integer optimization problems whose constraints and objective functions e 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.