Combinatorial Optimization: Matchings, Matroids and the Travelling Salesman (At the Crossroads of the Salesman and the Postman)

András Sebő, CNRS, Laboratoire G-SCOP, Francia

The course intends to provide second level fundamental knowledge of combinatorial optimization in an interactive way, alternating between lecture and exercise solving style. I will count on first grade knowledge of an introductory course in graph theory or optimization. I will proceed through concrete examples for most of the introduced problems, and give a number of exercises and problems.

The first, larger part of the course will be a Tour d'horizon around the main directions of advanced combinatorial optimization, hoping to have time for the details concerning non-bipartite matchings and their generalizations (to parity constrained subgraphs called T-joins) and matroids, used then in a complex application.

The main examples of this "tour d'horizon" will be:

• matchings in general (not necessarily bipartite) graphs (with an application from scheduling), good knowledge of bipartite matching will help quicker understanding,
• connectivity properties (2-connectivity of undirected and strong connectivity of directed graphs, ear theorems) and ...
• ... their application to the travelling salesman problem (we will understand  Christophides' 3/2 heuristic, a version for and sketch its modern improvements), the similar sounding and much easier ...
• ... Chinese Postman Problem,
• bin packing,
• maximum cut, and
• matroids.

The second part of the course is about the most recent developments concerning one of the celebrated "exposition" problems of the field, the Travelling Salesman Problem (TSP).  This is at the same time one particular Computer Science-type application, making deep use of several methods of combinatorial optimization that we will have learned. This part of the course deepens the acquired knowledge, uses the methods in a nontrivial way, and at the same time the reached results could be of primary interest for the students in computer science.

More concretely, as an application of the focus points of the course,  I will tell the best approximation algorithms  that recently broke the almost 40 years of silence since the appearance of Christofides' celebrated algorithm. The sudden progress is about minimum 2-edge-connected subgraphs or concerns the path TSP using the most important fundamental  tools of Combinatorial Optimization, matchings, matroids considered in the first part of the course, and also polyhedral methods, moreover random sampling, or the graph-metric special case, when Christofides' ratio is improved from 3/2 to 7/5. I am planning to draw a global picture of advanced combinatorial optimization, through concrete examples, pointing out the sensitive points that contribute to our intuition.

Nuevo! Material de "pre-calentamiento" para el curso, disponible haciendo click aquí.

Acerca del profesor

András Sebő, PhD of the Eötvös Loránd University (Budapest, Hungary, 1987) has been working for the CNRS (Grenoble, France) since 1988. He is the head of the combinatorial optimization team of the G-SCOP laboratory, and is a honorary member of the EGRES research group (Eötvös Loránd University, Budapest). He has spent time at universities in Germany, North America, Israel and Japan. His main research subjects have been various objects of combinatorial optimization and graph theory such as matchings, the postman problem (T-joins), disjoint path problems (routing), connections to polyhedral combinatorics and number theory (the Lonely Runner, Hilbert bases, empty simplices), and lately approximation algorithms for bin packing and the TSP.