Approximating the metric TSP in linear time

DOI10.1007/s00224-010-9289-0zbMath1227.68029OpenAlexW2054572608MaRDI QIDQ649110

Davide Bilò, Guido Proietti, Luca Forlizzi

Publication date: 30 November 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9289-0

zbMATH Keywords

traveling salesman problemNP-hardnessmetric graphslinear-time approximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem

Uses Software

• TSPLIB
• Concorde
• Blossom V

Cites Work

• Unnamed Item
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Approximation algorithms for the watchman route and zookeeper's problems.
• On the approximability of the traveling salesman problem
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• The Travelling Salesman and the PQ-Tree
• Sublinear time algorithms for metric space problems
• Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio
• A linear-time approximation algorithm for weighted matchings in graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• TSPLIB—A Traveling Salesman Problem Library
• Faster scaling algorithms for general graph matching problems
• The Traveling Salesman Problem with Distances One and Two
• Fast minimum-weight double-tree shortcutting for metric TSP
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP