Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality

DOI10.1007/978-3-642-03367-4_41zbMath1253.68364OpenAlexW1545532356MaRDI QIDQ3183477

Łukasz Kowalik, Marcin Mucha

Publication date: 20 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_41

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (2)

From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization

Cites Work

• Unnamed Item
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• On the relationship between ATSP and the cycle cover problem
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
• On Approximating Restricted Cycle Covers
• Algorithms – ESA 2005

This page was built for publication: Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality