Graduiertenkolleg: Methods for Discrete Structures

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


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

Abstract:
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

Abstract:
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