The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

DOI10.1137/130913328zbMath1350.68288arXiv1112.0699OpenAlexW3102803201MaRDI QIDQ2817793

Robert Krauthgamer, Lee-Ad J. Gottlieb, Yair Bartal

Publication date: 2 September 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.0699

zbMATH Keywords

traveling salesmanapproximation algorithmhierarchies

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (12)

Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ A Modern View on Stability of Approximation ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ Time complexity of the analyst's traveling salesman algorithm ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Unnamed Item ⋮ Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling dimension ⋮ Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension ⋮ Non-uniform packings

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• The Euclidean traveling salesman problem is NP-complete
• Nearest neighbor queries in metric spaces
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• Ahlfors \(Q\)-regular spaces with arbitrary \(Q>1\) admitting weak Poincaré inequality
• Worst-case analysis of a new heuristic for the travelling salesman problem
• On the approximability of the traveling salesman problem
• Deformable spanners and applications
• Searching dynamic point sets in spaces with bounded doubling dimension
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Improved Inapproximability for TSP
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Bypassing the embedding
• 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
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
• The Traveling Salesman Problem with Distances One and Two
• Forbidden-set distance labels for graphs of bounded doubling dimension
• Solution of a Large-Scale Traveling-Salesman Problem
• Advances in metric embedding theory
• A tight bound on approximating arbitrary metrics by tree metrics
• Bilipschitz embeddings of metric spaces into space forms

This page was built for publication: The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme