Nonlinear discrete optimization I

Thursday, November 20, 2008 - 9:00am - 10:00am
EE/CS 3-180
Robert Weismantel (Otto-von-Guericke-Universität Magdeburg)
This talk is concerned with optimizing nonlinear
functions over the lattice points in a polyhedral set.

We present three families of polynomial time algorithms
for special cases of the general problem.
Each such algorithm makes use of
combinatorial, geometric or algebraic
properties of the underlying problem.

The first problem deals with optimizing nonlinear functions over a matroid.
(Joint work with Jon Lee and Shmuel Onn).
The second class of problems concerns convex n-fold
integer minimization problems.
(Joint work with Raymond Hemmecke and Shmuel Onn).
Our last family of problems is to maximize polynomials
over the integer points in a polytope when the dimension is fixed.
Under mild assumptions we present an FPTAS for performing this task.
(Joint work with Jesus De Loera, Matthias Koeppe and Raymond Hemmecke).
MSC Code: