Approximation algorithms for TSP with neighborhoods in the plane

DOI10.1016/S0196-6774(03)00047-6zbMath1079.68114arXiv1703.01640OpenAlexW3121675905MaRDI QIDQ4458874

Joseph S. B. Mitchell, Adrian Dumitrescu

Publication date: 14 March 2004

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

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

Mathematics Subject Classification ID

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

Related Items

A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring ⋮ On the minimum corridor connection problem and other generalized geometric problems ⋮ Robotic data mules for collecting data over sparse sensor fields ⋮ 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 ⋮ A novel discretization scheme for the close enough traveling salesman problem ⋮ Bi-objective data gathering path planning for vehicles with bounded curvature ⋮ An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem ⋮ A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods ⋮ Facility location problems on graphs with non-convex neighborhoods ⋮ Ordered \(p\)-median problems with neighbourhoods ⋮ A multi‐vehicle covering tour problem with speed optimization ⋮ Household-Level Economies of Scale in Transportation ⋮ The generalized close enough traveling salesman problem ⋮ Observation routes and external watchman routes ⋮ Minimum-perimeter intersecting polygons ⋮ Constant-Factor Approximation for TSP with Disks ⋮ The Shortest Separating Cycle Problem ⋮ Minimum covering with travel cost ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks ⋮ Dubins traveling salesman problem with neighborhoods: a graph-based approach ⋮ An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for The Close-Enough Traveling Salesman Problem ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Advances in Meter Reading: Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network ⋮ Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles ⋮ Cooperative TSP ⋮ Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks ⋮ The Travelling Salesman Problem for finite-sized cities ⋮ On the total perimeter of homothetic convex bodies in a convex container ⋮ APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS ⋮ Minimum cost \(b\)-matching problems with neighborhoods ⋮ Spatial coverage in routing and path planning problems ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods