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, February 4, 2008

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
MA 041

Lecture - 14:15

Martin Skutella - Technische Universität Berlin

Tree Routings in Virtual Private Network Design

Consider a communication network which is represented by an undirected graph with edge costs. Within this network there is a set of terminals which want to communicate with each other. However, the exact amount of traffic between pairs of terminals is not known in advance. Instead, each terminal has an upper bound on the cumulative amount of traffic that it can send or receive. The task is to specify a fixed communication path for any pair of terminals and to install capacities on the edges of the graph at minimum cost supporting any possible communication scenario. This problem is known as the Virtual Private Network Design Problem (VPN). The famous VPN Tree Routing Conjecture states that there always exists an optimal tree solution where the chosen communication paths form a tree spanning all terminals. Recently, in joint work with Fabrizio Grandoni, Volker Kaibel, and Gianpaolo Oriolo, we came up with a related conjecture that implies the VPN Tree Routing Conjecture (I talked about this at the MDS workshop in November). Only few weeks ago, Goyal, Olver, and Shepherd presented a proof of our conjecture which implies that the VPN Tree Routing Conjecture is true. Their proof is based on several interesting concepts and techniques from the area of Combinatorial Optimization. In this talk we give an introduction into the VPN problem and discuss this very recent result.

Colloquium - 16:00

Raman Sanyal - Technische Universitšt Berlin

Polytope projections and topological obstructions

Is it possible to Minkowski sum two triangles in the plane to a 9-gon? Like many problems regarding combinatorial/geometric properties of polytopes, this one can be phrased in terms of projections. We show how Gale duality helps translating questions concerning polytope projections into topological embeddability questions. As a sneak preview: The answer to the above question is "No" since the complete bipartite graph K_{3,3} is not planar.

Letzte Aktualisierung: 28.01.2008