Monday, December 7, 2015
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
The talk surveys and discusses a number of tractable special
cases of the travelling salesman problem and the quadratic
assignment problem. As a common theme, the underlying cost
matrices can be defined and easily understood through basic
linear algebra: they form cones, or low-dimensional subspaces,
or are of bounded max-plus rank.
Colloquium - 16:00
Abstract:
Separation in graphs is related to graphs being expanders. A conjecture
by Kalai generalizes the planar separation theorem to simple polytopes. It
states that the graph of a simple d-polytope can be separated to two
roughly equal parts by removing O(n^((d-2)/(d-1))) vertices. We provide a
counterexample to this conjecture. This is joint work with Günter
Ziegler.