Fouad Mardini on Christofides on The Travelling Salesman

Fouad Mardini on "Worst-case analysis of a new heuristic for the traveling salesman problem" by Nicos Christofides

The Traveling Salesman Problem might very well be the most studied problem in combinatorial optimization. Much of this interest comes from the fact that the TSP is an NP hard problem, yet the TSP is studied on its own merits as it has applications in many fields.

We will use the paper of Christofides as a starting point to discuss the NP complexity class and approximation algorithms to intractable problems. Christofides algorithm is simple and elegant, yet gives the best known approximation ratio for the symmetric TSP.

Along the way we will detour into graph matchings and other interesting tidbits such as Aurora's Euclidean TSP approximation scheme and the Held-Karp LP relaxation.

If you are coming, please sign up at Skills Matter also https://skillsmatter.com/meetups/7906-worst-case-analysis-of-a-new-heuristic-for-the-traveling-salesman-problem-by-nicos-christofides

Fouad Mardini currently works as a software engineer in London. He recently finished studying for a Masters in CS at Bonn, where he developed his interest in combinatorial optimization.