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 Bernoulli Center Lausanne, the 11th Cargese Workshop on Combinatorial Optimization, and elsewhere. See here, here, and here.
    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.

  • ``From TSP to Vehicle Routing - Theory and Practice''.
    Lecture held at the Bill Cook birthday workshop. See here, here, and here.
    Abstract: Over the past few years, our understanding of the approximability of the TSP and natural extensions has improved substantially. Our survey will also include recently discovered reductions, including the first improvement for capacitated vehicle routing since the 1980s, as well as open problems. Moreover, we outline our techniques for handling vehicle routing instances in industrial practice, with many constraints and time-dependent travel times.

  • ``Resource Sharing, Routing, Chip Design''.
    Lectures held at the University of Waterloo, ETH Zurich, and elsewhere. See here, here, and here.
    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.