Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


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

Robert Weismantel - ETH Zürich

Optimization of nonlinear functions over lattice points in convex or polyhedral sets

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

Iskander Aliev - Cardiff University

Lattice points in knapsack polyhedra and k-Frobenius numbers

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.



Letzte Aktualisierung: 24.04.2015