SFB 303 Discussion Paper No. B-248

Author: Schürger, Klaus
Title: The Traveling Salesman Problem for Unbounded Random Points
Abstract: Let X_1,X_2... denote a sequence of independent identically distributed random points in R^d, d \geq 2. Let L_n denote the Euclidean length of the shortest path through X1,...,X_n. We investigate the asymptotic behaviour of L_n when the distribution of X1 has a noncompact support. Recently W. Rhee noted that there is an interesting relation between L_n, its median and the Hamming metric. In this way, the nice large deviation properties of the Hamming metric become efficient for L_n. Along these lines we obtain conditions which guarantee that lim[n to infinity] L_n/E[L_n]=1 completely when the distribution of X_1 has a noncompact support
Keywords: traveling salesman problem, tsp, Hamming metric
JEL-Classification-Number:
Creation-Date: 10.3.1993
Unfortunately this paper is not available. Please order a hardcopy via e-mail.

SFB 303 Homepage