On the fluctuations of the stochastic traveling salesperson problem

On the fluctuations of the stochastic traveling salesperson problem

0.00 Avg rating—0 Votes
Article ID: iaor1992328
Country: United States
Volume: 16
Issue: 3
Start Page Number: 482
End Page Number: 489
Publication Date: Aug 1991
Journal: Mathematics of Operations Research
Authors:
Keywords: probability, programming: network
Abstract:

Consider n points X1,...,Xn independently and uniformly distributed on the unit square [0,1]2. Denote by Tn the length of the shortest tour through X1,...,Xn. We prove that for some universal constant k, we have P(ℝTn-E(Tn)ℝ≥K’-1exp(¸-t2K) whenever t•K’-1n1’/2.

Reviews

Required fields are marked *. Your email address will not be published.