Jens Vygen: [English Homepage] [Deutsche Homepage] [Publications] [Projects] [Students] [Courses] Lectures [Committees]

Recent lectures:

  • ``Approximation Algorithms for Traveling Salesmen''.
    Lectures held at Diamond Veenendaal, FRICO Osnabrück, FIM Zürich, and elsewhere [PDF-File]
    Abstract: For the famous traveling salesman problem (TSP), Christofides' 1976 algorithm with approximation ratio 3/2 is still the best we know, and the 4/3 conjecture is still completely open. But recently there has been progress on interesting variants. We will review the state of the art and open problems. In particular, we focus on approximation algorithms for the the s-t-path TSP, in which start and end of the tour are given and not identical.

  • ``Resource Sharing, Routing, Chip Design''.
    Various lectures held at MIT, TU Berlin, INP Grenoble, University of Waterloo, University of Magdeburg, University of Darmstadt, FRICO Osnabrück, and elsewhere [updated PDF-File]
    Abstract: Chip design is one of the most fascinating application areas of mathematics. One important task is routing. Interconnecting millions of sets of pins by wires is challenging because of the huge instance sizes and limited resources. The graphs can have billions of vertices; moreover, even the simplest special cases of the routing problem are NP-hard. We show how to model the routing problem by min-max resource sharing and present a simple combinatorial fully polynomial approximation scheme which is both faster and more general than all previous algorithms. Using this we compute overall routing solutions that are far superior to those computed by industrial routing tools.

Selected previous invited lectures and tutorials:

Vorträge für Kinder und Jugendliche:

See here for lecture courses at the University of Bonn.