An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
DOI10.1016/J.JDA.2005.07.004zbMATH Open1275.90076OpenAlexW2056215713MaRDI QIDQ866548FDOQ866548
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
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Network flows. Theory, algorithms, and applications.
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Approximation algorithms for the TSP with sharpened triangle inequality
- Title not available (Why is that?)
- 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.
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (20)
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- 35/44-approximation for asymmetric maximum TSP with triangle inequality
- Title not available (Why is that?)
- On the maximum TSP with \(\gamma\)-parameterized triangle inequality
- Title not available (Why is that?)
- Title not available (Why is that?)
- An improved approximation algorithm for the maximum TSP
- Minimum-Weight Cycle Covers and Their Approximability
- Approximation algorithms for multi-criteria traveling salesman problems
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality
- Deterministic algorithms for multi-criteria TSP
- Minimum-weight cycle covers and their approximability
- A new approximation algorithm for the asymmetric TSP with triangle inequality
- Approximability of the minimum-weight \(k\)-size cycle cover problem
- Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions
- Two Approximation Algorithms for ATSP 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
- Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
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)
