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

DOI10.1016/J.JDA.2005.07.004MaRDI QIDQ866548zbMATH OpenOpenAlexFDO

Authors 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

strengthened triangle inequalitytraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2038707
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• scientific article; zbMATH DE number 2086388
• 35/44-approximation for asymmetric maximum TSP with triangle inequality

Cites work

• Approximation algorithms for the TSP with sharpened triangle inequality
• scientific article; zbMATH DE number 2185604 (Why is no real title available?)
• scientific article; zbMATH DE number 3564899 (Why is no real title available?)
• scientific article; zbMATH DE number 2038707 (Why is no real title available?)
• scientific article; zbMATH DE number 2086388 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• 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
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.

Cited in

(23)

• Minimum-weight cycle covers and their approximability
• Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Deterministic algorithms for multi-criteria TSP
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Minimum-Weight Cycle Covers and Their Approximability
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
• scientific article; zbMATH DE number 2038707 (Why is no real title available?)
• scientific article; zbMATH DE number 2079394 (Why is no real title available?)
• scientific article; zbMATH DE number 2086388 (Why is no real title available?)
• A new approximation algorithm for the asymmetric TSP with triangle inequality
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• 35/44-approximation for asymmetric maximum TSP with triangle inequality
• Parameterized approximations for the minimum diameter vertex-weighted Steiner tree problem in graphs with parameterized weights
• On the maximum TSP with -parameterized triangle inequality
• An improved approximation algorithm for the k-supplier problem with parameterized triangle inequality
• An improved two-stage approximation algorithm for the k-supplier problem with parameterized triangle inequality
• Constant-ratio polynomial time approximation of the asymmetric minimum weight cycle cover problem with limited number of cycles
• On the relationship between ATSP and the cycle cover problem
• An improved approximation algorithm for the maximum TSP

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

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