An improved approximation algorithm for the ATSP with parameterized triangle inequality

DOI10.1016/J.JALGOR.2008.10.002MaRDI QIDQ3497512zbMATH OpenOpenAlexFDO

Authors Tongquan Zhang, Weidong Li, Jianping Li

Publication date 24 July 2009

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

Full work available at URL https://doi.org/10.1016/j.jalgor.2008.10.002

zbMATH Keywords

approximation algorithmparameterized triangle inequalitytraveling salesman problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

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

Cited in

(20)

• Lower tolerance-based branch and bound algorithms for the ATSP
• 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
• 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 2086388 (Why is no real title available?)
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• An improved approximation algorithm for ATSP
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• 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
• 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 maximum TSP

This page was built for publication: An improved approximation algorithm for the ATSP with parameterized triangle inequality

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