Probabilistic analysis of solving the assignment problem for the traveling salesman problem

This paper deals with probabilistic analysis of optimal solutions of the asymmetric traveling salesman problem. The exact distribution for the number of required next-best solutions of the assignment problem with random data in order to find an optimal tour is given. For every n-city asymmetric problem, there exists an algorithm such that (i) with probability 1 ? s, s?(0,1) the algorithm produces an optimal tour, (ii) it runs in time $\text{O}\text{(}\text{n}{}^4\text{3}\text{)}$, and (iii) it requires less than w((w + n ? 1)$\text{log}\text{(w + n ? 1) + w + 1) +}\text{1}\text{6}\text{w(n}{}^3\text{+ 3n}{}^2\text{+ 2n ? 6)}$ computational steps, where w = log(s)/log(1 ? E_n); E_n ?(0,1) is given by a simple mathematical formula. Additionally, the polynomial of (iii) gives the exact (deterministic) execution time to find w =1 ,2…. next-best solutions of the assignment problem.