Date：3/14（Tue）14:00-
Venue：,Room Dw601, IIS, University of Tokyo
Invited Speaker：Prof. Hayato Takahashi (Tokyo Institute of Technology)

Title：Hausdorff dimension and the Stochastic Traveling  
Salesman Problem

Abstract：The traveling salesman problem is a problem of  
finding the shortest tour through given points.
In 1959, Beardwood, Halton, and Hammersley studied asymptotic length  
of the shortest tour through points on Euclidean space.
In particular they described the optimal tour length with Euclidean  
dimension for the case that points are distributed with respect to Lebesgue absolutely  
continuous measure.
In this paper we reinterpret and generalize their results in terms of  
fractal geometry.
We give the asymptotic order of the optimal tour length in terms of  
Hausdorff dimension.