A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
Abstract
In “An Improved Approximation Algorithm for TSP,” Karlin, Klein, and Oveis Gharan design the first improvement over the classical 1.5 approximation algorithm of Christofides-Serdyukov after more than 40 years. Their algorithm first chooses a random spanning tree from the maximum entropy distribution of spanning trees with marginals equal to the optimum LP solution of TSP, and then, similar to Christofides’ algorithm, it adds the minimum cost matching on the odd degree vertices of the tree. To analyze their simple algorithms, they prove and exploit new tools from the theory of strongly Rayleigh distributions.
Topics & Concepts
Spanning treeMathematicsApproximation algorithmMinimum spanning treeTravelling salesman problemCombinatoricsMatching (statistics)Metric (unit)AlgorithmTree (set theory)Mathematical optimizationStatisticsOperations managementEconomicsComplexity and Algorithms in GraphsOptimization and Packing ProblemsVehicle Routing Optimization Methods