Lectures and Colloquia during the semester

**June 18, 2001**

Technische Universität Berlin

Straße des 17. Juni 136, 10623 Berlin

Math building - Room MA 042

** Lecture - 14:15**

### Volker Strassen - Universität Konstanz

### Degeneration of linear and bilinear maps

*Abstract:*
Classification problems of linear algebra, such as those leading to
the Jordan and Kronecker normal forms, find their natural place in the
representation theory of quivers, dating from the early seventies.
Degeneration of a hyperbola to a pair of straight lines is an instance
of a principle that plays an important role in modern geometry.
We will give an introduction to representations of quivers and their
degeneration, then shift to an asymptotic point of view and resort to the
asymptotic spectrum, a data structure that unifies geometry and computational
complexity of bilinear maps, in particular of matrix multiplication.

** Colloquium - 16:00**

### Lisa Fleischer -

### Approximating Minimum Cost Vertex Connectivity

*Abstract:*
In reliable network design, it is desired to
build efficiently a network that stays connected
even under a specified number of node or link failures.
A natural formulation of this problem includes
the Steiner tree problem as a special case, so is not
only NP-hard, but is also hard to approximate to
within an arbitrarily small constant factor of optimal.
We develop factor 2 approximation algorithms for some non-trivial
special cases: the survivable network design problem
studied by Monma and Shallcross, and Grotschel, Monma, Stoer in which
all connectivity requirements are in the set {0,1,2};
and the element connectivity problem introduced by
Jain, et al. in which only links and Steiner nodes may fail.
This improves on previous approximation guarantees
of 3 and log |V| respectively, and match the best
known approximation guarantees for the easier problem
when only links may fail. We will also discuss
the possibility of extending our techniques to
more general vertex connectivity problems.

[top]