Space filling curve heuristic and the traveling salesman problem
Loading...
Date
2012.
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2012.
Abstract
Let LSFC n denote the length of the path connecting n random points uniformly distributed over the unit square obtained by the space lling curve heuristic. For a Hilbert type of space lling curve such as; Peano, Moore, Sierpinski and Polya, we prove that for some number K, we have, for all ... ; where K depends only on the space ling curve. This thesis is motivated by the work of Gao and Steele [1], where they found an almost Gaussian tail bound for a broad class of space lling curves. By adapting the method of Rhee and Talagrand [2], we have obtained an exact Gaussian tail bound for the length of the path obtained by the space lling curve..