On the complexity of approximating TSP with neighborhoods and related problems

DOI10.1007/s00037-005-0200-3zbMath1137.90753OpenAlexW2141791003MaRDI QIDQ853644

Oded Schwartz, Shmuel Safra

Publication date: 17 November 2006

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-005-0200-3

zbMATH Keywords

TSPapproximationNP-optimization problemshardness of approximationinapproximabilityTSP with neighborhoods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Two-level rectilinear Steiner trees ⋮ Observation routes and external watchman routes ⋮ Constant-Factor Approximation for TSP with Disks ⋮ The Shortest Separating Cycle Problem ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ On the complexity of the selective graph coloring problem in some special classes of graphs ⋮ EXISTENCE AND COMPUTATION OF TOURS THROUGH IMPRECISE POINTS ⋮ Online covering salesman problem ⋮ Cooperative TSP

This page was built for publication: On the complexity of approximating TSP with neighborhoods and related problems