Euclidean Travelling Salesman Problem with Location-Dependent and Power-Weighted Edges

Consider $$n$$ n nodes $$\{X_i\}_{1 \le i \le n}$$ { X i } 1 ≤ i ≤ n independently distributed in the unit square $$S,$$ S , each according to a density $$f$$ f , and let $$K_n$$ K n be the complete graph formed by joining each pair of nodes by a straight line segment. For every edge $$e$$ e in $$K_n$$ K n , we associate a weight $$w(e)$$ w ( e ) that may depend on the individual locations of the endvertices of $$e$$ e and is not necessarily a power of the Euclidean length of $$e.$$ e . Denoting $$\mathrm{TSP}_n$$ TSP n to be the minimum weight of a spanning cycle of $$K_n$$ K n corresponding to the travelling salesman problem (TSP) and assuming an equivalence condition on the weight function $$w(\cdot ),$$ w ( · ) , we prove that $$\mathrm{TSP}_n$$ TSP n appropriately scaled and centred converges to zero almost surely and in mean as $$n \rightarrow \infty .$$ n → ∞ . We also obtain upper and lower bound deviation estimates for $$\mathrm{TSP}_n.$$ TSP n .