Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality

DOI10.1007/978-3-642-03367-4_41MaRDI QIDQ3183477zbMATH OpenOpenAlexFDO

Authors Ł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

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

Recommendations

• scientific article; zbMATH DE number 2038707
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• scientific article; zbMATH DE number 2086388
• 35/44-approximation for asymmetric maximum TSP with triangle inequality

Cites work

• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
• Algorithms – ESA 2005
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• scientific article; zbMATH DE number 2038707 (Why is no real title available?)
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• On Approximating Restricted Cycle Covers
• On the relationship between ATSP and the cycle cover problem

Cited in

(10)

• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• scientific article; zbMATH DE number 2038707 (Why is no real title available?)
• scientific article; zbMATH DE number 2086388 (Why is no real title available?)
• An improved approximation algorithm for ATSP
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• On the relationship between ATSP and the cycle cover problem

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

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