In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is also NP-hard. In this paper, we present new approximation results for the TSPN, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a PTAS for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). Our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. Further, we give a linear-time O(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines. A salesman wants to meet a set of n potential buyers. Each buyer specifies a connected region in the plane, his neighborhood, within which he is willing to meet the salesman. For example, the neighborhoods may be disks centered at buyers' locations, and the radius of each disk specifies the maximum distance a buyer is willing to travel to the meeting place. The salesman wants to find a tour of shortest length that visits all of buyers' neighborhoods and finally returns to its initial departure point. A variant of the problem, which we will address in this paper, is that in which no departure point is specified, and only a tour of the neighborhoods is to be found. This problem, which is known as the TSP with neighborhoods (TSPN), is a generalization of the classic Euclidean Traveling Salesman Problem (TSP), in which the regions, or "neighborhoods," are single points, and consequently is NP-hard [9, 21] . The TSP has a long and rich history of research in combinatorial optimization. It has been studied extensively in many forms, including geometric instances; see [4, 13, 14, 20, 24] . The problem is known to be NP-hard, even for points in the Euclidean plane [9, 21] . It has * This work was done while the author was a visiting faculty member at Stony Brook University. † Partially supported by grants from HRL Laboratories, NASA Ames, the National Science Foundation (CCR-9732220), Northrop-Grumman Corporation, Sandia National Labs, and Sun Microsystems. Arkin and Hassin [1] were the first to study approximation algorithms for the geometric TSPN. They gave O(1)-approximation algorithms for several special cases, including parallel segments of equal length, translates of a convex region, translates of a connected region, and more generally, for regions which have diameter segments that are parallel to a common direction, and the ratio between the longest and the shortest diameter is bounded by a constant. For the general case of connected polygonal regions, Mata and Mitchell [15] obtained an O(log n)-approximation algorithm, based on "guillotine rectangular subdivisions", with time bound O(N 5 ), where N is the total complexity of the n regions. Gudmundsson and Levcopoulos [10] have recently obtained a faster method, which, for any fixed ǫ > 0, is guaranteed to perform at least one of the following tasks 1 : (1) it outputs a tour of length at most O(log n) times optimum in time O(n log n + N ); (2) it outputs a tour of length at most (1 + ǫ) times optimum in time O(N 3 ). So far, no polynomial-time approximation algorithm is known for general connected regions. Recently it was shown that TSPN is APX-hard and cannot be approximated within a factor of 1.000374 unless P=NP [5, 11] . In fact, the inapproximability factor for the vertex cover problem in graphs with degree bounded by 5, as stated in [7] , and on which the result in [11] is based, implies a factor larger than that. In the time since this paper first appeared, it has been shown by de Berg et. al [5] that the TSPN has an O(1)-approximation algorithm in the case that the regions are the regions are connected, disjoint, convex and fat. Also, Schwartz and Safra [25] have improved the lower bounds of [5, 11] on the hardness of approximation of several variants of the TSPN problem, and Jonsson [12] has given an O(n) time √ 2-approximation algorithm for the case of regions that are lines in the plane; our previous O(n) time π/2-approximation algorithm appears in Section 5. In this paper, we obtain several approximation results on the geometric TSPN, including: (1) We extend the approaches initiated in [1] and obtain the first O(1)-approximation algorithm for the TSPN having connected regions of the same or similar diameter. This solves among others, the open problem posed in [1] , to provide a constant-factor approximation algorithm for TSPN on segments of the same length and arbitrary orientation.
There exists a PTAS for TSPN when the neighborhoods are disjoint unit disks REF .
Approximation algorithms for TSP with neighborhoods in the plane
Journal of Algorithms, Volume 48, Issue 1, August 2003, Pages 135-159. (special issue for SODA 2001)
Mathematics Computer Science