Fall 2017

Improved Approximation Algorithms for the TSP and S-t-path TSP

Tuesday, Sep. 12, 2017 9:30 am10:30 am

Add to Calendar

Recent years have shown remarkable progress in the design and analysis of approximation algorithms for the graphical metric TSP and the general metric case of the s-t-path TSP. We will survey a number of these results, focusing in particular on the s-t-path TSP, where these results have seen the improvements to Christifides' algorithm yield a performance guarantee essentially matching the integrality gap of the standard LP relaxation.