APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS

DOI10.1142/S0218195909002897zbMath1172.65028OpenAlexW2113076619MaRDI QIDQ3636315

Khaled M. Elbassioni, Aleksei V. Fishkin, R. A. Sitters

Publication date: 30 June 2009

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195909002897

zbMATH Keywords

approximation algorithmsEuclidean traveling salesman problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (5)

Observation routes and external watchman routes ⋮ Constant-Factor Approximation for TSP with Disks ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ The travelling salesman problem with neighbourhoods: MINLP solution ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters

Cites Work

• Approximation algorithms for the Geometric Covering Salesman Problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Approximation algorithms for TSP with neighborhoods in the plane
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• TSP with neighborhoods of varying size

This page was built for publication: APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS