Title | ||
---|---|---|
FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/s10107-007-0175-8 | Math. Program. |
Keywords | Field | DocType |
mixed-integer set,non-negative polynomial,mixed-integer point,polynomial-time approximation scheme,fixed dimension,convex polytopes,integer programming in fixed,. mixed-integer nonlinear programming,weaker notion,arbitrary polynomial,optimizing polynomial,convex polytope,fully polynomial time approximation scheme | Integer,Approximation algorithm,Discrete mathematics,Combinatorics,Mathematical optimization,Polynomial,Nonlinear programming,Convex set,Polytope,Convex polytope,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
115 | 2 | 1436-4646 |
Citations | PageRank | References |
6 | 0.59 | 13 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jesús A. De Loera | 1 | 357 | 42.24 |
Raymond Hemmecke | 2 | 275 | 22.34 |
Matthias KöPpe | 3 | 191 | 20.95 |
Robert Weismantel | 4 | 964 | 90.05 |