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 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=1+terms of order q^{3/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