Analyzing the Max Entropy Algorithm for TSP

I will discuss recent progress on approximating the metric traveling salesperson problem, focusing on a line of work beginning in 2011 that studies the behavior of the max entropy algorithm. This algorithm is a randomized variant of the beautiful Christofides-Serdyukov algorithm from the 1970s which adds a minimum cost matching to the odd vertices of a minimum cost spanning tree.

After giving a survey of important concepts and results, I will sketch a proof that the max entropy algorithm is a better-than-3/2 approximation for metric TSP. This sketch will particularly emphasize the utility of viewing the max entropy distribution over spanning trees as a polynomial with a zero-free region. I will also discuss recent work on lower bounds and derandomization, as well as highlight open directions. We are still far from understanding the worst case performance of this algorithm.

Based on joint works with Anna Karlin, Shayan Oveis Gharan, Leonid Gurvits, Jonathan Leake, Billy Jin, and David Williamson.