Skip to main content
1 of 1
Yonatan N
  • 101
  • 2
  • 5

In the 65-page paper A Randomized Rounding Approach to the Traveling Salesman Problem, Oveis Gharan, Saberi, and Singh acquire a $(1.5 - 10^{-52})$-approximation algorithm for the Traveling Salesman Problem on graphical metrics, a problem for which a $1.5$ approximation can be explained and analyzed in under 5 minutes. I have heard that the constant can be improved to $1.5 - 10^{-6}$ with little change to the paper.

Since then, a sequence of simpler works has brought the constant down to 1.4 (which I believe is the latest result).

Yonatan N
  • 101
  • 2
  • 5