Probabilistic analysis of the longest hamiltonian tour problem
Rakesh Vohra · Networks · 1988
Abstract 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 → ∞.