The travelling salesman problem on a randomly diluted lattice
Deepak Dhar, Mustansir Barma, Barnali Chakrabarti, A. Taraphder · Journal of Physics A Mathematical and General · 1987
The authors study the problem of a travelling salesman who must visit a randomly chosen subset of sites of a d-dimensional lattice. The average length of the shortest path per chosen site is alpha (q) where (1-q) is the density of chosen sites. For a triangular lattice, they show that alpha (q) differs from 1 only by terms of order q 5 . For the square lattice, they show that, to first order in q, optimal paths can be found from the dynamics of a model of a one-dimensional gas of kinks and antikinks. The authors find alpha (q) or=L/3(1-q) -1/2 as q tends to 1.