The travelling salesman problem on a randomly diluted lattice

Dhar, D. ; Barma, M. ; Chakrabarti, B. K. ; Taraphder, A. (1987) The travelling salesman problem on a randomly diluted lattice Journal of Physics A: Mathematical and General, 20 (15). pp. 5289-5298. ISSN 0305-4470

Full text not available from this repository.

Official URL: http://iopscience.iop.org/0305-4470/20/15/040

Related URL: http://dx.doi.org/10.1088/0305-4470/20/15/040

Abstract

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 q5. 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=1+terms of order q3/2. They also obtain a constructive upper bound valid for all q, which gives alpha (q)>or=L/3(1−q)−½ as q tends to 1.

Item Type:Article
Source:Copyright of this article belongs to Institute of Physics.
ID Code:82185
Deposited On:10 Feb 2012 04:13
Last Modified:13 Jul 2012 13:32

Repository Staff Only: item control page