Approximating the metric TSP in linear time

DOI10.1007/S00224-010-9289-0zbMATH Open1227.68029OpenAlexW2054572608MaRDI QIDQ649110FDOQ649110

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

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

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)

Cites Work

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

Cited In (12)

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

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)