Y8a4imvxspxbobrbzwid
SkillsCast

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.

YOU MAY ALSO LIKE:

Thanks to our sponsors

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

Fouad Mardini

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.

SkillsCast

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.

YOU MAY ALSO LIKE:

Thanks to our sponsors

About the Speaker

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

Fouad Mardini

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.