Approximation algorithms for TSP with neighborhoods in the plane
arXiv:1703.01640 · doi:10.1016/s0196-6774(03)00047-6
Abstract
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.
Manuscript that was published in J. Algorithms (2003), with brief clarifying remarks added (2014)
Cited by in corpus (6)
- Accessing From The Sky: A Tutorial on UAV Communications for 5G and Beyond
- Trajectory Optimization for Completion Time Minimization in UAV-Enabled Multicasting
- TSP With Locational Uncertainty: The Adversarial Model
- A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane
- Star Routing: Between Vehicle Routing and Vertex Cover
- Visual Monitoring for Multiple Points of Interest on a 2.5D Terrain using a UAV with Limited Field-of-View Constraint