Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T09:21:42.415Z Has data issue: false hasContentIssue false
  • English
  • Français

Travelling Salesman with a Self-Similar Itinerary

Published online by Cambridge University Press:  27 July 2009

Steven P. Lalley
Steven P. Lalley
Affiliation:
Department of Statistics Purdue University, West Lafayette, Indiana 47907
Get access Rights & Permissions [Opens in a new window]

Extract

Let X1, X2,… be i.i.d. random points in R2 with distribution v, and let Ln be the length of the shortest path through X1,…, Xn. The exact almost sure rate of growth of Ln, is obtained under the assumption that v is self-similar in an appropriate sense. This extends a well-known theorem of Beardwood, Halton, and Hammersley.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 1 , January 1990 , pp. 1 - 18
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Beardwood, J., Halton, J.H., & Hammersley, J.M. (1959). The shortest path through many points. Proceedings of the Cambridge Philosophical Society 55: 299–327.CrossRefGoogle Scholar
Bollobas, B. (1979), Graph theory. New York: Springer.CrossRefGoogle Scholar
Chungk, K.L. (1974). A course in probability theory, 2nd ed.New York: Academic Press.Google Scholar
Hutchinson, J. (1981). Fractals and self-similarity. Indiana University Mathematics Journal 30: 713–747.CrossRefGoogle Scholar
Karp, R.M. (1976). The probabilistic analysis of some combinatorial search algorithms. In Taub, F. (ed.), Proceedings symposium on new directions and recent results in algorithms and complexity. San Francisco, California: Academic Press.Google Scholar
Mandelbrot, B. (1983). The fractal geometry of nature. New York: Freeman.CrossRefGoogle Scholar
Steele, J.M. (1981). Complete convergence of short paths and Karp's algorithm for the TSP. Mathematics of Operations Research 6: 374–378.CrossRefGoogle Scholar