Algorithms for the symmetric traveling salesman problem

EADS Talk by Ola Svensson, assistant professor in the theory group at EPFL


The traveling salesman problem is one of the most fundamental optimization problems. In this lecture we will give an overview of classic approximation algorithms as well as novel approaches with improved  guarantees for special metrics. 

At the end, we will also discuss related open problems.

Short bio:

Ola Svensson is an assistant professor in the theory group at EPFL.  He is interested in fundamental questions in combinatorial optimisation related to the approximability of basic optimization problems. His work on the traveling salesman problem received the best paper award at FOCS'11.