
Recent survey lectures:
 ``Packing cycles in planar and boundedgenus graphs''
Lectures held at the University of Heidelberg and the Bernoulli Center Lausanne.
Abstract: We devise constantfactor approximation algorithms for finding as many
disjoint cycles as possible from a certain family of cycles in a given planar
or boundedgenus graph. Here disjoint can mean vertexdisjoint or
edgedisjoint, 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 constantfactor approximation algorithm
for vertexdisjoint paths in fully planar instances and approximate minmax theorems of the
ErdősPó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 CargesePorquerolles Workshop,
ETH Zurich,
and elsewhere
[updated PDFFile]
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 NPhard. We show how to model the routing problem by minmax 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:
 ``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 BlackBox Reductions''. Invited lecture at the 16th International Computer Science Symposium in Russia, Sochi 2021.
Also at the HIM trimester program on discrete optimization 2021
and the Tutte colloquium at the University of Waterloo 2022 [Video]
 ``Eardecompositions meet Tjoins: a proof of Frank's theorem''.
Distinguished lecture at the
Cargese Workshop on Combinatorial Optimization 2019
 ``Integrality ratios for the stpath TSP''.
Workshop on the traveling salesman problem, Banff 2018
[Video]
 ``Approaching 3/2 for the stpath TSP''
(SODA 2018).
Lecture held at London School of Economics,
at the University of Oxford,
and INP Grenoble, 20172018
 ``Better sttours by Gao trees''.
Lecture held at
FND Amsterdam, 2016
 ``Reassembling trees for the traveling salesman''.
Lecture held at
INP Grenoble,
ETH Zürich,
ISMP in Pittsburgh,
Connectivity Workshop in Bonn,
2015
[PDFFile]
[Video]
 ``Ears and tours''.
Workshop on Approximation Algorithms and the Hardness of Approximation,
Banff 2014
[Video]
 ``Smallest twoedgeconnected spanning subgraphs and the TSP''.
Workshop on Flexible Network Design, Fields Institute, Toronto, 2013
[Video]
[Interactive video]
 ``ddimensional arrangement revisited''. Lecture held at the Bellairs Workshop on Combinatorial Optimization, Geometry and Lattices, 2013
[PDFFile]
 ``Shorter Tours By Nicer Ears (Approximating GraphTSP and Related Problems)''.
Distinguished lecture series at the
Third Cargese Workshop on Combinatorial Optimization,
lectures at Paris VI, Cornell,
Columbia, and elsewhere, 20122013
[PDFFile]
 ``Faster Algorithm for Optimum Steiner Trees''.
Lecture held at the
14th Aussois Workshop on Combinatorial Optimization
and elsewhere, 20102013
[PDFFile]
 ``Combinatorial Optimization in Chip Design''. Keynote lecture at the
23rd European Conference on Operational Research (EURO 2009)
[PDFFile]
 ``Mathematics of Routing''. Series of four lectures at the
Spring School
on Mathematics of Chip Design,
Hangzhou 2009
[PDFFile 1]
[PDFFile 2]
[PDFFile 3]
[PDFFile 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
[PDFFile]
 ``Combinatorial Optimization and Applications in VLSI Design''.
Lectures at the
ADONET Spring School,
Budapest 2006
[PDFFile]
 ``Approximation Algorithms for Facility Location''.
Lectures at the
Oberwolfach Workshop on Combinatorial Optimization 2005,
and the
NHC Spring School and Workshop,
Tokyo 2006
[PDFFile]
Ausgewählte Vorträge für Kinder, Jugendliche, und Nichtfachleute:
