A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
DOI10.1007/S00454-011-9337-9zbMATH Open1233.68215OpenAlexW3138698442MaRDI QIDQ650109FDOQ650109
Authors: T.-H. Hubert Chan, Khaled 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
Recommendations
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- A PTAS for TSP with neighborhoods among fat regions in the plane
- Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
- Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
- A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
- On the complexity of approximating TSP with neighborhoods and related problems
- On the complexity of approximating TSP with neighborhoods and related problems
- Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension
- On Approximating the TSP with Intersecting Neighborhoods
- A (slightly) improved approximation algorithm for metric TSP
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)
Cites Work
- On hierarchical routing in doubling metrics
- Polylogarithmic inapproximability
- Plongements lipschitziens dans ${\bbfR}\sp n$
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Geometry of cuts and metrics
- A tight bound on approximating arbitrary metrics by tree metrics
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- A PTAS for TSP with neighborhoods among fat regions in the plane
- Approximation algorithms for TSP with neighborhoods in the plane
- A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Title not available (Why is that?)
- Approximation algorithms for the Geometric Covering Salesman Problem
- TSP with neighborhoods of varying size
- Automata, Languages and Programming
- Nearest neighbor queries in metric spaces
- The complexity of the free space for motion planning amidst fat obstacles
- The black-box complexity of nearest-neighbor search
- Bypassing the embedding
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of approximating TSP with neighborhoods and related problems
- Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
- APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
- Fast construction of nets in low dimensional metrics, and their applications
Cited In (8)
- Mallows-smoothed distribution over rankings approach for modeling choice
- Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
- Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
- Near-optimal algorithms for the assortment planning problem under dynamic substitution and stochastic demand
- Constant-factor approximation for TSP with disks
- Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
This page was built for publication: A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650109)
