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
关键词
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
相关论文
共 20 条
[1]  
Barvinok A., 1999, Math. Sci. Res. Inst. Publ., V38, P91
[3]  
BELLARE M, COMPLEXITY NUMERICAL
[4]  
COX D, 1992, IDEALS VARIETIES ALG
[5]   A PTAS for the minimization of polynomials of fixed degree over the simplex [J].
de Klerk, Etienne ;
Laurent, Monique ;
Parrilo, Pablo A. .
THEORETICAL COMPUTER SCIENCE, 2006, 361 (2-3) :210-225
[6]   Integer polynomial optimization in fixed dimension [J].
De Loera, JA ;
Hemmecke, R ;
Köppe, M ;
Weismantel, R .
MATHEMATICS OF OPERATIONS RESEARCH, 2006, 31 (01) :147-153
[7]   Effective lattice point counting in rational convex polytopes [J].
De Loera, JA ;
Hemmecke, R ;
Tauzer, J ;
Yoshida, R .
JOURNAL OF SYMBOLIC COMPUTATION, 2004, 38 (04) :1273-1302
[8]   Short rational functions for toric algebra and applications [J].
De Loera, JA ;
Haws, D ;
Hemmecke, R ;
Huggins, P ;
Sturmfels, B ;
Yoshida, R .
JOURNAL OF SYMBOLIC COMPUTATION, 2004, 38 (02) :959-973
[9]  
Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[10]  
HASTAD J, 1997, P 29 ANN ACM S THEOR, P1