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

Monday Lecture and Colloquium

Monday, July 1, 2013

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Jesus A. De Loera - University of California, Davis

Recent advances in the geometry of linear programming

Linear programming is undeniably a central tool of applied mathematics and a source of many fascinating mathematical problems. In this talk I will present several advances from the past 5 years in the geometry of linear optimization. These results include new results on the diameter of polyhedra regarding the simplex method, the differential geometry of central paths of interior point methods, and about the geometry of some less well-known iterative techniques. One interesting feature of these advances is that they connect this very applied algorithmic field with algebraic geometry, differential geometry, and combinatorial topology.

I will try to summarize work by many authors and will include results that are my own joint work with subsets of the following people A. Basu, M. Junod, S. Klee, B. Sturmfels, and C. Vinzant.

Colloquium - 16:00

Arnau Padrol - Freie Universität Berlin

Many neighborly polytopes and Delaunay triangulations

In this talk I will present a simple way to construct a large family of neighborly polytopes. It can be used to show that the number of (combinatorial types of vertex labeled) neighborly d-polytopes with n vertices is at least (n-1)^{d(n-d-1)(1/2+o(1))}, which is the current best lower bound for the number of d-polytopes with n vertices.

I will also show how these polytopes can be realized with all their vertices on a sphere. This implies that the same bounds also hold for the number of combinatorial types of (d-1)-dimensional neighborly Delaunay triangulations. This is based on collaborative work with Bernd Gonska.

Letzte Aktualisierung: 18.06.2013