Recent survey lectures:
- ``Approximation Algorithms for Traveling Salesmen''.
Various lectures (with similar content) held at
[PDF-File, not containing our new result (SODA 2018) yet]
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 (with similar content) held at MIT,
University of Waterloo,
University of Magdeburg,
University of Darmstadt,
the 2017 Cargese-Porquerolles Workshop,
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:
- ``Approaching 3/2 for the s-t-path TSP''.
Lecture held at London School of Economics and at the University of Oxford, 2017. Upcoming in SODA 2018.
- ``Better s-t-tours by Gao trees''.
Lecture held at
FND Amsterdam, 2016
- ``Reassembling trees for the traveling salesman''.
Lecture held at
ISMP in Pittsburgh,
Connectivity Workshop in Bonn,
- ``Ears and tours''.
Workshop on Approximation Algorithms and the Hardness of Approximation,
- ``Smallest two-edge-connected spanning subgraphs and the TSP''.
Workshop on Flexible Network Design, Fields Institute, Toronto, 2013
- ``d-dimensional arrangement revisited''. Lecture held at the Bellairs Workshop on Combinatorial Optimization, Geometry and Lattices, 2013
- ``Shorter Tours By Nicer Ears (Approximating Graph-TSP and Related Problems)''.
Invited lecture series at the
Third Cargese Workshop on Combinatorial Optimization,
lectures at Paris VI, Cornell,
Columbia, and elsewhere, 2012-2013
- ``Faster Algorithm for Optimum Steiner Trees''.
Lecture held at the
14th Aussois Workshop on Combinatorial Optimization
and elsewhere, 2010-2013
- ``Combinatorial Optimization in Chip Design''. Keynote lecture at the
23rd European Conference on Operational Research (EURO 2009)
- ``Mathematics of Routing''. Series of four lectures at the
on Mathematics of Chip Design,
- ``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),
- ``Combinatorial Optimization and Applications in VLSI Design''.
Lectures at the
ADONET Spring School,
- ``Approximation Algorithms for Facility Location''.
Lectures at the
Oberwolfach Workshop on Combinatorial Optimization 2005,
NHC Spring School and Workshop,
Vorträge für Kinder und Jugendliche: