Complete Convergence of the Directed TSP

Consider the random directed graph G_n whose vertices X₁, …, X_n are independent uniformly distributed over [0, 1]². For 1 ≤ i < j ≤ n, the orientation of the edge X_iX_j is selected at random, independently for each edge and independently of the X_i's. Denote by U_n the length of the shortest path through G_n. Then for some constant β > 0 and all ε > 0 we have ∑_n≥1P(|n^−1/2U_n − β| > ε) < ∞.