On the complexity of approximating TSP with neighborhoods and related problems
DOI10.1007/S00037-005-0200-3zbMATH Open1137.90753OpenAlexW2141791003MaRDI QIDQ853644FDOQ853644
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
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
TSPapproximationinapproximabilityhardness of approximationNP-optimization problemsTSP with neighborhoods
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)
Cited In (22)
- On the complexity of approximating TSP with neighborhoods and related problems
- TSP with neighborhoods of varying size
- The shortest separating cycle problem
- On the Approximation Hardness of Some Generalizations of TSP
- Online covering salesman problem
- Cooperative TSP
- Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems
- Two-level rectilinear Steiner trees
- Observation routes and external watchman routes
- The Angular-Metric Traveling Salesman Problem
- Constant-factor approximation for TSP with disks
- Observation routes and external watchman routes
- Title not available (Why is that?)
- On the complexity of the selective graph coloring problem in some special classes of graphs
- Existence and computation of tours through imprecise points
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
- Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
- Approximation algorithms for TSP with neighborhoods in the plane
- Title not available (Why is that?)
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- Approximation algorithms for the Geometric Covering Salesman Problem
- On the \({\mathcal {H}}\)-free extension complexity of the TSP
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)
