Approximation algorithms for the Geometric Covering Salesman Problem

DOI10.1016/0166-218X(94)90008-6zbMath0819.90115MaRDI QIDQ1343140

Esther M. Arkin, Refael Hassin

Publication date: 1 February 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

covering salesmantour of minimum length

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (51)

Building bridges between convex regions ⋮ On the minimum corridor connection problem and other generalized geometric problems ⋮ A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem ⋮ A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance ⋮ BALANCED PARTITION OF MINIMUM SPANNING TREES ⋮ TRAVELING SALESMAN PROBLEM OF SEGMENTS ⋮ A novel discretization scheme for the close enough traveling salesman problem ⋮ Bi-objective data gathering path planning for vehicles with bounded curvature ⋮ Approximation Algorithms for Generalized MST and TSP in Grid Clusters ⋮ Scheduling last-mile deliveries with truck-based autonomous robots ⋮ Constrained optimization with integer and continuous variables using inexact restoration and projected gradients ⋮ Time constrained maximal covering salesman problem with weighted demands and partial coverage ⋮ Budget constrained minimum cost connected medians ⋮ Controlled mobility in stochastic and dynamic wireless networks ⋮ Connectivity graphs of uncertainty regions ⋮ 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 ⋮ Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods ⋮ Facility location problems on graphs with non-convex neighborhoods ⋮ A multi‐vehicle covering tour problem with speed optimization ⋮ The generalized close enough traveling salesman problem ⋮ A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane ⋮ A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem ⋮ Observation routes and external watchman routes ⋮ Minimum-perimeter intersecting polygons ⋮ Shortest Paths in Graphs of Convex Sets ⋮ Constant-Factor Approximation for TSP with Disks ⋮ The Shortest Separating Cycle Problem ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ The kissing problem: how to end a gathering when everyone kisses everyone else goodbye ⋮ An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for The Close-Enough Traveling Salesman Problem ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Approximation schemes for the generalized traveling salesman problem ⋮ Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles ⋮ An integer programming-based local search for the covering salesman problem ⋮ Mind the gap: a study of tube tour ⋮ The travelling salesman problem with neighbourhoods: MINLP solution ⋮ Cooperative TSP ⋮ On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane ⋮ A branch-and-cut algorithm for the maximum covering cycle problem ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ The Generalized Covering Salesman Problem ⋮ APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS ⋮ The vehicle routing-allocation problem: A unifying framework ⋮ Coverage path planning algorithms for agricultural field machines ⋮ Routing for unmanned aerial vehicles: touring dimensional sets ⋮ On the longest spanning tree with neighborhoods ⋮ Minimum cost \(b\)-matching problems with neighborhoods ⋮ Spatial coverage in routing and path planning problems ⋮ Approximation algorithms for lawn mowing and milling ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Watchman routes under limited visibility
• The Euclidean traveling salesman problem is NP-complete
• An extension of Christofides heuristic to the k-person travelling salesman problem
• The swapping problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Tight bounds for christofides' traveling salesman heuristic
• The Covering Salesman Problem

This page was built for publication: Approximation algorithms for the Geometric Covering Salesman Problem