Probabilistic Analysis of the Longest Hamiltonian Tour Problem

In this paper we study the probabilistic behavior of the farthest neighbor heuristic for finding the longest Hamiltonian tour in a graph. We assume the edge weights are independent random variables uniformly distributed in [0,1]. If F, is the length of the heuristic tour and L, the optimal tour then Fn/Ln 1 a.s. as n . We also show that Ln/n 1 a.s. as n .