A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
From MaRDI portal
Publication:650109
DOI10.1007/s00454-011-9337-9zbMath1233.68215OpenAlexW3138698442MaRDI 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 metricsquasi-polynomial time approximation schemetraveling salesman problem with neighborhoods
Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (4)
Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice ⋮ Constant-Factor Approximation for TSP with Disks ⋮ 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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
