Approximation algorithms for TSP with neighborhoods in the plane

DOI10.1016/S0196-6774(03)00047-6zbMATH Open1079.68114arXiv1703.01640OpenAlexW3121675905MaRDI QIDQ4458874FDOQ4458874

Joseph S. B. Mitchell, Adrian Dumitrescu

Publication date: 14 March 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1703.01640

Recommendations

• Approximation algorithms for TSP with neighborhoods in the plane
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• TSP with neighborhoods of varying size
• A PTAS for TSP with neighborhoods among fat regions in the plane
• scientific article; zbMATH DE number 1947392

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25)

Cited In (47)

• On the complexity of approximating TSP with neighborhoods and related problems
• TSP with neighborhoods of varying size
• Household-Level Economies of Scale in Transportation
• Constant-Factor Approximation for TSP with Disks
• On minimum- and maximum-weight minimum spanning trees with neighborhoods
• The Travelling Salesman Problem for finite-sized cities
• Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks
• Title not available (Why is that?)
• A PTAS for Euclidean TSP with Hyperplane Neighborhoods
• Building bridges between convex regions
• A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring
• Cooperative TSP
• A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods
• Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles
• The Shortest Separating Cycle Problem
• Dubins traveling salesman problem with neighborhoods: a graph-based approach
• Observation routes and external watchman routes
• Title not available (Why is that?)
• Minimum covering with travel cost
• A novel discretization scheme for the close enough traveling salesman problem
• APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
• A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance
• Data-driven optimization and statistical modeling to improve meter reading for utility companies
• THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE
• Ordered \(p\)-median problems with neighbourhoods
• Bi-objective data gathering path planning for vehicles with bounded curvature
• Minimum-perimeter intersecting polygons
• Approximation algorithms for lawn mowing and milling
• Observation routes and external watchman routes
• Automata, Languages and Programming
• On the minimum corridor connection problem and other generalized geometric problems
• An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem
• A multi‐vehicle covering tour problem with speed optimization
• Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks
• New approximation results for the maximum scatter TSP
• Approximation algorithms for TSP with neighborhoods in the plane
• Robotic data mules for collecting data over sparse sensor fields
• On finding a shortest isothetic path and its monotonicity inside a digital object
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• Minimum cost \(b\)-matching problems with neighborhoods
• Approximation algorithms for the Geometric Covering Salesman Problem
• Advances in Meter Reading: Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network
• Facility location problems on graphs with non-convex neighborhoods
• Spatial coverage in routing and path planning problems
• The generalized close enough traveling salesman problem
• On the total perimeter of homothetic convex bodies in a convex container
• An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for The Close-Enough Traveling Salesman Problem

This page was built for publication: Approximation algorithms for TSP with neighborhoods in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4458874)