Published November 16, 2007 | Version v1
Journal article

Fluctuations in the site-disordered traveling salesman problem

  • 1. Laboratoire de Physique Theorique, UMR CNRS 5152, IRSAMC, Universite Paul Sabatier, 118 route de Narbonne, 31062 Toulouse Cedex 04 (France)
  • 2. Harrow School of Computer Science, University of Westminster, Harrow HA1 3TP (United Kingdom)

Description

We extend a previous statistical mechanical treatment of the traveling salesman problem by defining a discrete 'site-disordered' problem in which fluctuations about saddle points can be computed. The results clarify the basis of our original treatment, and illuminate but do not resolve the difficulties of taking the zero-temperature limit to obtain minimal path lengths

Additional details

Identifiers

DOI
10.1088/1751-8113/40/46/002;
PII
S1751-8113(07)58182-5;

Publishing Information

Journal Title
Journal of Physics. A, Mathematical and Theoretical (Online)
Journal Volume
40
Journal Issue
46
Journal Page Range
p. 13837-13857
ISSN
1751-8121

INIS

Country of Publication
United Kingdom
Country of Input or Organization
International Atomic Energy Agency (IAEA)
INIS RN
39028888
Subject category
S71: CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSICS;
Descriptors DEI
FLUCTUATIONS; GRAPH THEORY; LINEAR PROGRAMMING; MATHEMATICAL LOGIC
Descriptors DEC
CALCULATION METHODS; MATHEMATICS; VARIATIONS