The Traveling Salesman
and
Related Stochastic Problems

Abstract

In the traveling salesman problem, one must find the length of the shortest closed tour visiting given ``cities''. We study the stochastic version of the problem, taking the locations of cities and the distances separating them to be random variables drawn from an ensemble. We consider first the ensemble where cities are placed in Euclidean space. We investigate how the optimum tour length scales with number of cities and with number of spatial dimensions. We then examine the analytical theory behind the random link ensemble, where distances between cities are independent random variables. Finally, we look at the related geometric issue of nearest neighbor distances, and find some remarkable universalities.

Foreword, Table of Contents, and Chapter I: Introduction (gzip'd postscript, 156K)
Chapter II (Part 1): Scaling laws in the Euclidean TSP (gzip'd postscript, 551K)
Chapter II (Part 2): Scaling laws in the Euclidean TSP (gzip'd postscript, 479K)
Chapter II (Part 3): Scaling laws in the Euclidean TSP (gzip'd postscript, 458K)
Chapter III: The random link TSP and its analytical solution (gzip'd postscript, 222K)
Chapter IV: Universalities in nearest neighbor distances, Appendices and Bibliography (gzip'd postscript, 242K)

The thesis as a single postscript file (gzip'd, 1797K)
The same but in French, sort of (gzip'd, 1818K)

I have been promising for a while to create an HTML version of the thesis, but this project is now on hold. Instead, I expect in the near future to make available a fully hyperlinked PDF version.

Last modified: 25 October 1999

The Traveling Salesman and Related Stochastic Problems

Abstract

The Traveling Salesman
and
Related Stochastic Problems