35/44-approximation for asymmetric maximum TSP with triangle inequality

DOI10.1007/s00453-009-9306-3zbMath1206.68367OpenAlexW2149302127MaRDI QIDQ627544

Marcin Mucha, Łukasz Kowalik

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9306-3

zbMATH Keywords

approximation algorithmtraveling salesman problemATSPasymmetric maximum TSP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (4)

Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem ⋮ Limitations of incremental dynamic programming ⋮ Approximation of the double traveling salesman problem with multiple stacks

Cites Work

• Unnamed Item
• Matching theory
• Better approximations for max TSP
• A \(\frac78\)-approximation algorithm for metric Max TSP
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP
• An -approximation algorithm for the asymmetric maximum TSP
• Algorithms and Data Structures
• Algorithms – ESA 2005

This page was built for publication: 35/44-approximation for asymmetric maximum TSP with triangle inequality