A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
From MaRDI portal
Publication:650109
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
Cites work
- scientific article; zbMATH DE number 2064408 (Why is no real title available?)
- scientific article; zbMATH DE number 1775442 (Why is no real title available?)
- scientific article; zbMATH DE number 1436138 (Why is no real title available?)
- scientific article; zbMATH DE number 6469222 (Why is no real title available?)
- A PTAS for TSP with neighborhoods among fat regions in the plane
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
- A tight bound on approximating arbitrary metrics by tree metrics
- APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
- Approximation algorithms for TSP with neighborhoods in the plane
- Approximation algorithms for the Geometric Covering Salesman Problem
- Automata, Languages and Programming
- Bypassing the embedding
- Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
- Fast construction of nets in low dimensional metrics, and their applications
- Geometry of cuts and metrics
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Nearest neighbor queries in metric spaces
- On hierarchical routing in doubling metrics
- On the complexity of approximating TSP with neighborhoods and related problems
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Polylogarithmic inapproximability
- TSP with neighborhoods of varying size
- The black-box complexity of nearest-neighbor search
- The complexity of the free space for motion planning amidst fat obstacles
Cited in
(8)- 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
- Mallows-smoothed distribution over rankings approach for modeling choice
- Constant-factor approximation for TSP with disks
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
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)
