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

zbMATH Keywords

NP-hardnessmetric graphslinear-time approximation algorithmsTraveling Salesman Problem (TSP)

Mathematics Subject Classification ID

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)

Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio

Uses Software

• TSPLIB

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