A (slightly) improved approximation algorithm for metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
Abstract
For some > 10−36 we give a randomized 3/2− approximation algorithm for metric TSP.
Topics & Concepts
Approximation algorithmMetric (unit)Computer scienceAlgorithmEngineeringOperations managementAdvanced Graph Theory ResearchComplexity and Algorithms in GraphsLimits and Structures in Graph Theory