Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 26, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Robert Hildebrand
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.
Joint work with: Alberto Del Pia (University of Wisconsin-Madison), Robert Weismantel (ETH Zurich), and Kevin Zemmer (ETH Zurich).
Automatic MiSe System Software Version 1.4803M | admin login