Euclidean TSP (part I)

Marios Papaefthymiou and Mike Kluger-man. 1 Euclidean TSP Consider the travelling salesman problem in the plane. Given n points in the plane, we would like to nd a tour that visits all of them and that minimizes the distance travelled, where the distance between two points is given by the Euclidean distance. This problem will be denoted by ETSP (Euclidean TSP). In a companion set of notes, we will present very recent algorithms of Arora and Mitchell that produce in polynomial time a tour which is within 1+ of the optimum, for any xed > 0. In this set of notes, we rst present some preliminaries and older related results. Before we continue, we should point out that it is not known whether the Euclidean TSP is in NP. Even if we are presented with a candidate tour for the \yes-no " version of the problem, we do not know how to avoid computing a possibly exponential number of decimal digits, in order to calculate the square root required for the Euclidean distance. First, we present an algorithm which generates a path of length no more than p N k (k a constant to be determined) given that the points all lie within a unit square. Here we use the \Strips Method". First, break the square down int