Monday, June 1, 2015
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
This talk deals with the problem of optimizing convex, concave or polynomial functions over the lattice points in convex or polyhedral sets.
In a first part we discuss convex mixed integer optimization problems.
When we aim at minimizing a convex function
over mixed-integer points in convex sets we derive optimality
conditions that lead to a formal concept of duality based on lattice free polyhedra.
Another focus of the talk is about optimizing polynomial
functions over the lattice points in a polyhedron.
We explain why the
problem is already hard in dimension two for polynomial functions of
degree four..
Then we will discuss how to solve the problem in polynomial
time when the function is a quadratic polynomial in two variables.
Further complexity results about optimizing homogeneous polynomials and
cubic polynomials over the integer points in polyhedra in dimension two
will be presented too.
Colloquium - 16:00
Abstract:
The well-studied affine semigroup $\sg(A)=\{ b : b=Ax, \ x \in \Z^n, x \geq 0\}$ can be stratified by the sizes of the polyhedral fibers $IP_A(b)=\{x: Ax=b, x\geq 0, x\in \Z^n\}$.
In this talk we discuss a structure theory that characterizes precisely the set $\sg_{\geq k}(A)$ of all vectors $b \in \sg(A)$ such that their fiber $IP_A(b)$ contains \emph{at least} k lattice points.
As a corollary, we prove that for fixed n,k the k-Frobenius number can be computed in polynomial time, generalising a well-known result of Ravi Kannan.
This is a joint work with Jesus De Loera and Quentin Louveaux.