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.