Equidistribution in all dimensions of worst-case point sets for the traveling salesman problem

Equidistribution in all dimensions of worst-case point sets for the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor19961053
Country: United States
Volume: 8
Issue: 4
Start Page Number: 678
End Page Number: 683
Publication Date: Nov 1995
Journal: SIAM Journal On Discrete Mathematics
Authors: ,
Abstract:

Given a set S of n points in the unit square [0,1]’d, an optimal traveling salesman tour of S is a tour of S that is of minimum length. A worst-case point set for the traveling salesman problem in the unit square is a point set S’(n’) whose optimal traveling salesman tour achieves the maximum possible length among all point sets Sℝ[0,1]’d, where ℝSℝ=n. An open problem is to determine the structure of S’(n’). The authors show that for any rectangular parallelepiped R contained in [0,1]’d, the number of points in S’(n’)ℝR is asymptotic to n times the volume of R. Analogous results are proved for the minimum spanning tree, minimum-weight matching, and rectilinear Steiner minimum tree. These equidistribution theorems are the first results concerning the structure of worst-case point sets like S’(n’).

Reviews

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