Analyzing the Max Entropy Algorithm for TSP - Nathan Klein

Computer Science/Discrete Mathematics Seminar II

Topic: Analyzing the Max Entropy Algorithm for TSP
Speaker: Nathan Klein
Affiliation: Institute for Advanced Study
Date: February 20, 2024

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.

Видео Analyzing the Max Entropy Algorithm for TSP - Nathan Klein канала Institute for Advanced Study