#
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

*Abstract:*

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

*Abstract:*

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