On the complexity of approximating TSP with neighborhoods and related problems

DOI10.1007/S00037-005-0200-3MaRDI QIDQ853644zbMATH OpenOpenAlexFDO

Authors 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

TSPapproximationinapproximabilityhardness of approximationNP-optimization problemsTSP with neighborhoods

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of approximating TSP with neighborhoods and related problems
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• TSP with neighborhoods of varying size

Cited in

(22)

• On the complexity of approximating TSP with neighborhoods and related problems
• TSP with neighborhoods of varying size
• On the Approximation Hardness of Some Generalizations of TSP
• Cooperative TSP
• Existence and computation of tours through imprecise points
• Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems
• The Angular-Metric Traveling Salesman Problem
• scientific article; zbMATH DE number 1559518 (Why is no real title available?)
• On the complexity of the selective graph coloring problem in some special classes of graphs
• Observation routes and external watchman routes
• Constant-factor approximation for TSP with disks
• The shortest separating cycle problem
• Two-level rectilinear Steiner trees
• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• Approximation algorithms for TSP with neighborhoods in the plane
• Online covering salesman problem
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• Observation routes and external watchman routes
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
• Approximation algorithms for the Geometric Covering Salesman Problem

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

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