Approximating the metric TSP in linear time
From MaRDI portal
Publication:649110
DOI10.1007/s00224-010-9289-0zbMath1227.68029MaRDI QIDQ649110
Guido Proietti, Davide Bilò, 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
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Uses Software
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
