Sankhya: The Indian Journal of Statistics

1995, Volume 57, Series A, Pt. 1, pp. 33--40

TWO ASYMPTOTIC INEQUALITIES FOR THE STOCHASTIC TRAVELLING SALESMAN PROBLEM

By

W. STADJE, University of Osnabrück

SUMMARY.  Let Tn be the length of the shortest closed path through the n i.i.d. random points X1, ...., Xn in $\Re_d$. Under slight conditions on the density of the (possibly unbounded) Xi asymptotic upper and lower bounds for E(Tn)/n(d-1)/d are given.

AMS (1990) subject classification.  Primary 60D05; secondary  65K25, 68Q25.

Key words and phrases. Stochastic traveling salesman problem, asymptotic behavior, inequality, unbounded case.

Full paper (PDF)

This article in mathematical reviews.