A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
From MaRDI portal
Publication:650109
DOI10.1007/s00454-011-9337-9zbMath1233.68215MaRDI QIDQ650109
T.-H. Hubert Chan, Khaled M. Elbassioni
Publication date: 25 November 2011
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-011-9337-9
doubling metrics; quasi-polynomial time approximation scheme; traveling salesman problem with neighborhoods
90C27: Combinatorial optimization
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
Constant-Factor Approximation for TSP with Disks, Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice, Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic Demand, The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of approximating TSP with neighborhoods and related problems
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Nearest neighbor queries in metric spaces
- Approximation algorithms for the Geometric Covering Salesman Problem
- The complexity of the free space for motion planning amidst fat obstacles
- The black-box complexity of nearest-neighbor search
- Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
- Bypassing the embedding
- Polylogarithmic inapproximability
- APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
- Plongements lipschitziens dans ${\bbfR}\sp n$
- 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
- Fast construction of nets in low dimensional metrics, and their applications
- A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
- TSP with neighborhoods of varying size
- Automata, Languages and Programming
- Geometry of cuts and metrics
- A tight bound on approximating arbitrary metrics by tree metrics
