Approximating the metric TSP in linear time

DOI10.1007/S00224-010-9289-0MaRDI QIDQ649110zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luca Forlizzi, Guido Proietti

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)

Recommendations

• Approximating the Metric TSP in Linear Time
• Fast minimum-weight double-tree shortcutting for metric TSP, Is the best one good enough?
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 1500530
• Deterministic 7/8-approximation for the metric maximum TSP

Cites work

• scientific article; zbMATH DE number 1500530 (Why is no real title available?)
• A linear-time approximation algorithm for weighted matchings in graphs
• Approximation algorithms for the watchman route and zookeeper's problems.
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP
• Fast minimum-weight double-tree shortcutting for metric TSP, Is the best one good enough?
• Faster scaling algorithms for general graph matching problems
• Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
• On the approximability of the traveling salesman problem
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Sublinear time algorithms for metric space problems
• TSPLIB—A Traveling Salesman Problem Library
• The Traveling Salesman Problem with Distances One and Two
• The travelling salesman and the PQ-tree.

Cited in

(12)

• On the Complexity of the Metric TSP under Stability Considerations
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• scientific article; zbMATH DE number 1754594 (Why is no real title available?)
• scientific article; zbMATH DE number 7651222 (Why is no real title available?)
• Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
• A (slightly) improved approximation algorithm for metric TSP
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP
• TSP with bounded metrics
• Fast minimum-weight double-tree shortcutting for metric TSP, Is the best one good enough?
• Simple linear time approximation algorithm for betweenness
• Priority functions for the approximation of the metric TSP
• Approximating the Metric TSP in Linear Time

Describes a project that uses

Uses Software

• TSPLIB
• Concorde
• Blossom V

This page was built for publication: Approximating the metric TSP in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q649110)