Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Complexity of Polynomial Minimization Over Integer Points in PolyhedraOptimization
|Speaker: ||Robert Hildebrand, ETH Zurich|
|Location: ||3106 MSB|
|Start time: ||Wed, Jun 11 2014, 4:10PM|
We focus on the complexity of the problem of minimizing a polynomial function over integer points in a polyhedron. This problem is known to be NP-hard even fixed dimension two and degree four. Recently, Del Pia and Weismantel showed that for fixed dimension two and degree two, this problem can be solved in polynomial time. We continue this classification of problems that can be solved in polynomial time in fixed dimension by determining the complexity for minimizing cubic polynomials and homogeneous polynomials in dimension two over integer points in a polyhedron.
Co-Authors: Alberto Del Pia (IBM Research), Robert Weismantel (ETH Zurich), and Kevin Zemmer (ETH Zurich)