A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane

2017/03/05 by Mitchell, Joseph S. B.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1703.01646

Abstract

The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of n regions (\em 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 P_i has area Ω([diam(P_i)]²), but is otherwise arbitrary.

Related

• The guillotine approach for TSP with neighborhoods revisited
• A PTAS for Euclidean TSP with Hyperplane Neighborhoods
• A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
• The traveling salesman problem for lines and rays in the plane
• The traveling salesman problem for lines, balls and planes