An improved approximation algorithm for the maximum TSP

DOI10.1016/j.tcs.2010.03.012zbMath1203.68318OpenAlexW1982624404MaRDI QIDQ974748

Ying Yin, Jianping Li, Tongquan Zhang

Publication date: 7 June 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.012

zbMATH Keywords

approximation algorithmmaximum traveling salesman problemparameterized triangle inequality

Mathematics Subject Classification ID

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

Related Items (1)

On the maximum TSP with \(\gamma\)-parameterized triangle inequality

Cites Work

• Unnamed Item
• An approximation algorithm for the maximum traveling salesman problem
• On the relationship between ATSP and the cycle cover problem
• An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits
• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• Deterministic 7/8-approximation for the metric maximum TSP
• On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• An -approximation algorithm for the asymmetric maximum TSP

This page was built for publication: An improved approximation algorithm for the maximum TSP