An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

DOI10.1016/j.jda.2005.07.004zbMath1275.90076OpenAlexW2056215713MaRDI QIDQ866548

Markus Bläser, Bodo Manthey, Jiří Sgall

Publication date: 14 February 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.07.004

zbMATH Keywords

traveling salesman problemstrengthened triangle inequality

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (11)

From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality ⋮ Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ On the relationship between ATSP and the cycle cover problem ⋮ Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs ⋮ Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Approximation algorithms for multi-criteria traveling salesman problems ⋮ Minimum-weight cycle covers and their approximability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the TSP with sharpened triangle inequality
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities

This page was built for publication: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality