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

Recent survey lectures:

  • ``Packing cycles in planar and bounded-genus graphs''
    Lectures held at the University of Heidelberg and the Bernoulli Center Lausanne.
    Abstract: We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be undirected or directed. The family of cycles under consideration must be uncrossable and allow for a certain oracle access. Our setting generalizes many problems that were studied separately in the past. Among our corollaries are the first constant-factor approximation algorithm for vertex-disjoint paths in fully planar instances and approximate min-max theorems of the Erdős-Pósa type.

  • ``Approximation Algorithms for Traveling Salesmen''.
    Various survey lectures (with simiar titles and contents) held at Diamond Veenendaal, FRICO Osnabrück, FIM Zürich, Oberwolfach, ISMP Bordeaux, ENS Paris, and elsewhere
    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 exciting progress on interesting variants. We will review the state of the art and open problems. In particular, we focus on approximation algorithms for the Path TSP, in which start and end of the tour are given and not identical.

  • ``Resource Sharing, Routing, Chip Design''.
    Various lectures (with similar content) held at MIT, TU Berlin, INP Grenoble, University of Waterloo, University of Magdeburg, University of Darmstadt, FRICO Osnabrück, the 2017 Cargese-Porquerolles Workshop, ETH Zurich, 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.

Some other invited lectures and tutorials:

Ausgewählte Vorträge für Kinder, Jugendliche, und Nichtfachleute:

See here for lecture courses at the University of Bonn.