Probabilistic Algorithm for the Directed Traveling Salesman Problem
John M. Steele · Mathematics of Operations Research · 1986
A model is given for a random directed traveling salesman problem (DTSP). The asymptotic behavior of the optimal solution of the DTSP is determined, and this result is used to establish an ϵ-optimal probabilistic algorithm for solving the DTSP in polynomial time.