Joseph S. B. Mitchell
ABSTRACT
The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of n regions (neighborhoods). We present the first polynomial-time approximation scheme for TSPN for a set of regions given by arbitrary disjoint fat regions in the plane. This improves substantially upon the known approximation algorithms, and is the first PTAS for TSPN on regions of non-comparable sizes. Our result is based on a novel extension of the m-guillotine method. The result applies to regions that are "fat" in a very weak sense: each region Pi contains a disk of radius Ω(diam(Pi)), but is otherwise arbitrary. Further, the result applies even if the regions intersect arbitrarily, provided that there exists a packing of disjoint disks, of radii Ω(diam(Pi)), contained within their respective regions. Finally, the PTAS result applies also to the case in which the regions are sets of points or polygons, each each lying within one of a given set of disjoint fat regions.
- A PTAS for TSP with neighborhoods among fat regions in the plane
Recommendations
A PTAS for Euclidean TSP with Hyperplane Neighborhoods
In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN ...
A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics
We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of n subsets (regions or neighborhoods) in the underlying metric space. We give a quasi-...
A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsWe consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of n subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when ...
Comments