FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
复制标题
DOI：
10.1007/s10107-007-0175-8
复制
发表时间：
2007-06
影响因子：
2.7
通讯作者：
J. D. Loera;R. Hemmecke;M. Köppe;R. Weismantel
中科院分区：
文献类型：
--
作者：
J. D. Loera;R. Hemmecke;M. Köppe;R. Weismantel
当变量数固定时，证明了凸多面体中混合整数集上非负多项式极大化问题的完全多项式时间逼近格式(FPTAS)的存在性。此外，利用较弱的逼近概念，我们证明了当变量数固定时，凸多面体中混合整数集上任意多项式的极大化或极小化问题的完全多项式时间逼近格式的存在性。
We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.