Approximating the Metric TSP in Linear Time
DOI10.1007/978-3-540-92248-3_5zbMath1202.90259OpenAlexW1819919459MaRDI QIDQ5302042
Guido Proietti, Luca Forlizzi, Davide Bilò
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_5
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (1)
Uses Software
Cites Work
- Approximation algorithms for the TSP with sharpened triangle inequality
- Approximation algorithms for the watchman route and zookeeper's problems.
- On the approximability of the traveling salesman problem
- The Travelling Salesman and the PQ-Tree
- 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
- Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP
This page was built for publication: Approximating the Metric TSP in Linear Time