University of Maryland
Friday, April 27 at 3:00 PM
Given a set of n disks of radius R in the Euclidean plane, the Traveling Salesman Problem With Neighborhoods (TSPN) on uniform disks asks for the shortest tour that visits all of the disks. The problem is a generalization of the classical Traveling Salesman Problem(TSP) on points and has been widely studied in the literature. For the case of disjoint uniform disks of radius R, Dumitrescu and Mitchell (SODA 2001) show that the optimal TSP tour on the centers of the disks is a 3.547-approximation to the TSPN version. The core of their analysis is based on bounding the detour that the optimal TSPN tour has to make in order to visit the centers of each disk and shows that it is at most 2Rn in the worst case. Häme, Hyytiä and Hakula(EuroCG 2011) asked whether this bound is tight when R is small and conjectures that it is at most 1.73Rn.
In this talk, we will further investigate this question and derive structural properties of the optimal TSPN tour to describe the cases in which the bound is smaller than 2Rn. Specifically, we will show that if the optimal TSPN tour is not a straight line, at least one of the following is guaranteed to be true: the bound is smaller than 1.999Rn or the TSP on the centers is a 2-approximation. We will identify local structures for which the detour term is large and then use their geometry to derive better lower bounds on the length of the TSPN tour. Finally, we will show how this leads to improved bounds on the Dumitrescu and Mitchell algorithm.