Traveling salesman problem across well-connected cities and with location-dependent edge lengths (Q2274794)

This paper studies traveling salesman problem (\(TSP\)) over cities spread across the unit square, each containing a subset of nodes. For integer \(n\ge1\), the unit square \(S\) is tiled into adjacent \(r_n\times r_n\) squares with intercity distance \(s_n\) spread evenly over the square. A subset of cities \(D_n(N)=\{S_{j1},\cdots,S_{jN}\}\) of the \(r_n\times r_n\) cities in \(\{S_l\}\) is called well-connected with intercity distance \(s_n\) if the induced subgraph \(G\) of the graph \(G_{ct}\), which is the graph of adjacent cities on the coordinate grid with the centers connected. With independently distributed \(n\) nodes, let \(TSPC_n\) represents the weight of the minimum weighted length cycle having the \(n\) nodes, in which the edge length between two nodes is location-dependent and based on an equivalent Euclidean metric over \(G\). It is shown that if the cities are well connected then \(TSPC_n\) appropriately centered and scaled converges to zero in probability. Some variance estimates and large deviation estimates are also derived. Some variance estimates and convergence in probability results for \(TSP\) are also obtained.