Monday, July 1, 2013
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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.