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 26th Combinatorial Optimization Workshop in Aussois, 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, at the Gerhard Woeginger Colloquium Aachen, and elsewhere. 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:

• ``Improved guarantees for the a priori TSP''. Workshop on Approximation Algorithms and the Hardness of Approximation, Banff 2023 [Video]
• ``Continuous approaches to VLSI routing''. Invited lecture at the HIM workshop on continuous approaches for discrete optimization, Bonn 2021 [Video]
• ``Traveling Salesman Problems: Approximation Algorithms and Black-Box Reductions''. Invited lectures at the 16th International Computer Science Symposium in Russia, Sochi 2021, the HIM trimester program on discrete optimization 2021, and the Tutte colloquium at the University of Waterloo 2022 [Video]
• ``Ear-decompositions meet T-joins: a proof of Frank's theorem''. Distinguished lecture at the Cargese Workshop on Combinatorial Optimization 2019
• ``Integrality ratios for the s-t-path TSP''. Workshop on the traveling salesman problem, Banff 2018 [Video]
• Approximation algorithms for the symmetric (path) TSP. Survey lecture at the Oberwolfach Workshop on Combinatorial Optimization 2018
• Approximation Algorithms for Traveling Salesmen. Invited talks at Diamond Symposium Veenendal, FRICO Osnabrück, and FIM Zürich, 2016 [PDF-File] [Video]
• ``Ears and tours''. Workshop on Approximation Algorithms and the Hardness of Approximation, Banff 2014 [Video]
• ``Smallest two-edge-connected spanning subgraphs and the TSP''. Workshop on Flexible Network Design, Fields Institute, Toronto, 2013 [Video]
• ``Shorter Tours By Nicer Ears (Approximating Graph-TSP and Related Problems)''. Distinguished lecture series at the Third Cargese Workshop on Combinatorial Optimization, lectures at Paris VI, Cornell, Columbia, and elsewhere, 2012-2013 [PDF-File]
• ``Combinatorial Optimization in Chip Design''. Keynote lecture at the 23rd European Conference on Operational Research (EURO 2009) [PDF-File]
• ``Mathematics of Routing''. Series of four lectures at the Spring School on Mathematics of Chip Design, Hangzhou 2009 [PDF-File 1] [PDF-File 2] [PDF-File 3] [PDF-File 4]
• ``Combinatorial Optimization in VLSI Placement and Routing''. Series of five lectures at the 45th Session of the Séminaire de Mathématiques Supérieures (NATO Advanced Study Institute), Montréal 2006 [PDF-File]
• ``Combinatorial Optimization and Applications in VLSI Design''. Lecture Series at the ADONET Spring School, Budapest 2006 [PDF-File]
• ``Approximation Algorithms for Facility Location''. Invited lectures at the Oberwolfach Workshop on Combinatorial Optimization 2005, and the NHC Spring School and Workshop, Tokyo 2006 [PDF-File]

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

• ``Neues vom Rundreiseproblem''. Mathe-Nacht, März 2021
• ``Was Würfel, Pyramiden und Fußbälle gemeinsam haben: Polyeder und die Euler-Formel''. Kinderuni Bonn, Februar 2011
• ``Drei Vorlesungen über Bäume''. Schülerwoche des Hausdorff Center for Mathematics, August 2009 [PDF-File]