MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms November 12, 1996 Lecture 15 Lecturer: Michel X. Goemans Scribe: Salil Vadhan Arora's (1 +E)-ApproximationScheme for the Euclidean TSP In the last lecture, we saw that, given any n points in [O, 112,Karp's partitioning algo- rithm finds a tour whose length is longer than the optimal tour by an additive factor of at most o(fi). In this lecture, we will see another partioning-based algorithm, due to Arora [I],which finds a tour of length at most (1+E) OPT in time no('/') for any E > 0. A similar result was also obtained by Mitchell. First, we observe that we can make some simplifying assumptions about the loca- tions of our cities. Given any finite set S of points in the plane, the bounding box of S is the smallest rectangle (with sides parallel to the coordinate axes) which contains all of S. The size of a rectangle is the length of its longest side. Claim 1 Suppose there is an approximation scheme1 for instances of the Euclidean TSP2 in which the n cities lie in a bounding box of size at most n2 and the distance between any two cities is at least 1, or 0. Then there is an approximation scheme for all instances of the Euclidean TSP. Proof: Clearly, we can scale to make the bounding box size n2 without changing the relative lengths of any tour. Moreover, if the bounding box was the smallest possible, the length OPT of the optimum tour is at least 2n2 (since there must be cities on the 2 shortest sides). Now, consider the instance obtained by rounding the coordinates of every city to the nearest integer. In the rounded instance, the distance between any two distinct cities is at least 1. Moreover, in the transformation, every city has moved by at most a/2.For any tour T, let 1(T)and l'(T) denote its length in the original and transformed instances respectively. Since we can perform an excursion from the new location to the old location of any city (or vice versa), we derive that lZ(T)-Z1(T)l5 fin. (1) Thus, if we have a (1+8)-approximation algorithm for the rounded instance, we get that the tour produced T has a length satisfying 'By approximation scheme, we mean a 1+€-approximation algorithm for any fixed E >0. 2We always mean the Euclidean TSP in two dimensions.OPT = (1+€')OPT+ (2+e1)JZn 5 (1+et)OPT+ (2+e1)JZ- 2n 1+el+ OPT 5 (1+~)n,2n whenever, for example, 6' = 0.86, 6 < 1, and n 2 1016 (but remember 6 is fixed so this last condition is not a problem). The partitioning in Arora's algorithm works differently than in Karp's algorithm. Arora's algorithm looks at what is called a '113: 213-tiling". Informally, a 113:213-tiling is a recursive partitioning of the bounding box into smaller rectangles by hor-izontal and vertical lines so that each line partition divides the longest side s of the corresponding rectangle into two pieces whose length is at least 113 the length of s. We also require that each vertical (resp. horizontal) line partition goes "slightly" to the left or to the right (resp. slightly above or below) of a city. Slightly, for example, can be understood as off by 612 where 6 represents the smallest gap between two dis-tinct x-or y-coordinates of cities. The goal of this is to allow only a small number of possible x-and y-coordinates for line partitions (namely 44, while avoiding the problem of having to assign cities that fall right on a line partition to either side of it. However, it may not be possible to have such a line partition and satisfy the 113:213 requirement. This is the reason for the somewhat complicated definition that follows. Definition 1 Let R be a rectangle in R2with sides parallel to the coordinate axes. Let s be the longest side of R and let is1 be its length. A line-partition of R is a partitioning of R into two smaller rectangles by a line-segment perpendicular to s and at a distance of 6 of a city. A line-partition P is valid iff one of the following conditions holds: 1. P divides s into two segments, each of length at least 1~113. 2. There are no line-partitions satisfying (1) and P can be moved to the center of the rectangle without crossing over any cities. A 113:213-tiling of a rectangle is a recursive partitioning of a rectangle by valid line-partitions until there is at most one city in the interior of any rectangle. (See Figure 1.) Figure 1 gives an example of a 113:213-tiling. Notice that line partition 3 does not divide the longest side of the corresponding rectangle into pieces of relative length at least 113. How deep can the recursion in a 113:213-tiling be? Note that the sizes of the rectangles need not decrease at each stage, because the first partition of a square produces two rectangles of the same size as the original square. Also, if the cities are all near the sides of the rectangle, no valid line-partition will cut the longest side s into pieces of length at least ls1/3. However, after at most four levels of recursion,Figure 1: A 113:213-tiling all the remaining rectangles will either have size at most 21~113or will have no cities in their interior. Observe that a rectangle of size 1/fi has at most one point in its interior. Thus the recursion has depth at most 4 (fin2)+ 1 = O(1ogn). The key theorem underlying Arora's algorithm will tell us that there is a near- optimal tour that doesn't cross any of the partitions we made too often and that we can find such the best such tour quickly. In order to make this precise, we need to specify the points at which we will allow crossings. Let m = rclognl~] for some constant c to be specified later. Divide each line segment drawn in our partition into m equally-sized segments. We call the midpoints of these segments portals. We will look at tours which cross our partition only at portals. Definition 2 A tour is called m-light (with respect to a given tiling) iff the following conditions hold: 1. Each line partition is crossed at most rn times and only at portals. 2. The tour is not self-crossing, but it may meet itself at portals. To clarify Part 2 of the above definition, see Figure 2. We allow a tour which goes from city a to city b and from city c to city d via portal p; this is an example of a tour which