FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

被引：8
|
作者：
De Loera, Jesus A. [2 ]
Hemmecke, Raymond [1 ]
Koeppe, Matthias [1 ]
Weismantel, Robert [1 ]
机构：
[1] Otto VonGuericke Univ Magdegurg, FMA IMO, D-39106 Magdeburg, Germany
[2] Univ Calif Davis, Dept Math, Davis, CA 95616 USA
来源：
MATHEMATICAL PROGRAMMING | 2008年 / 115卷 / 02期
基金：
美国国家科学基金会;
关键词：
mixed-integer nonlinear programming; integer programming in fixed dimension; computational complexity; approximation algorithms; FPTAS;
D O I：
10.1007/s10107-007-0175-8
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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.
引用
收藏
页码：273 / 290
页数：18
相关论文
共 50 条
12345