Integer Polynomial Optimization in Fixed Dimension
Integer Polynomial Optimization in Fixed Dimension
复制标题
DOI：
10.1287/moor.1050.0169
复制
发表时间：
2004-10
期刊：
影响因子：
--
通讯作者：
J. D. Loera;R. Hemmecke;M. Köppe;R. Weismantel
中科院分区：
文献类型：
--
作者：
J. D. Loera;R. Hemmecke;M. Köppe;R. Weismantel
我们分类，根据其计算复杂性，整数优化问题的约束条件和目标函数是多项式与整数系数，变量的数量是固定的。对于凸多面体格点上整数多项式的优化问题，给出了一个计算最优值上下界的算法。对于多面体上的非负多项式，这些边界序列导致优化问题的完全多项式时间近似方案。
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.