Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Fully polynomial time approximation schemes
for mixed-integer polynomial optimizationOptimization
|Speaker: ||Dr. Matthias Koeppe, Univ. Magdeburg/ UC Davis|
|Location: ||2112 MSB|
|Start time: ||Fri, Apr 21 2006, 12:10PM|
Integer linear optimization, that is the problem of optimizing a
linear functional over the integer points of a polyhedron, is NP-hard.
However, when we fix the number of variables, it can be solved in
polynomial time using the algorithm of Lenstra (1983). More strongly,
Khachiyan and Porkolab (2000) showed that convex polynomial functions
can be minimized over the integer points of convex semialgebraic sets
in polynomial time, when the number of variables is fixed.
The situation is different when we consider arbitrary (not necessarily
convex) objective functions over the integer points of a polytope.
Even when the dimension is fixed >= 2 and the degree is bounded <= 4,
the optimization problem is still NP-hard.
We prove the existence of a fully polynomial-time approximation scheme
(FPTAS) for the maximization problem where the objective function is
non-negative on the feasible region, when the dimension is fixed.
This is the strongest possible result, unless P=NP.
We then extend the FPTAS to the case of mixed-integer polynomial
optimization, where some of the variables are integers and some are
This is joint work with J. A. De Loera, R. Hemmecke, and R. Weismantel.