DMMP Seminar

Bodo Manthey — Space-Filling Curves for TSP without Space-Filling Curves

Time: Wednesday, April 17, 2013, 12:45-13:30
Location: Citadel, H311

Consider the traveling salesman problem (TSP) in d-dimensional Euclidean space: The n points are located in [0,1]^d, and the length of an edge between two points x and y is ||x-y||^p, i.e., the Euclidean distance between x and y raised to the power p. It is relatively easy to prove that there is always a TSP tour of length at most O(sqrt(n)) for d=2 and p=1. This can be generalized as follows: For every integer d>=1 and every p>0, there exists a TSP tour of length O(max(n^{(d-p)/d}), 1). The "standard" proof of this requires space-filling curves, more precisely Hölder continuous maps from [0,1] to [0,1]^d. However, these curves are quite counterintuitive objects. We try to give a proof of this result that does not use space-filling curves, but only approximations to them.