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, 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

Gerhard Woeginger - Technische Universiteit Eindhoven


Tractable special cases of QAP and TSP

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

Lauri Loiskekoski - Freie Universität Berlin


A graph of a simple polytope without small separators

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.


Letzte Aktualisierung: 30.11.2015