A (slightly) improved approximation algorithm for metric TSP

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

114 citations

Abstract

For some ǫ > 10 -36 we give a randomized 3/2ǫ approximation algorithm for metric TSP.