An improved approximation algorithm for the maximum TSP

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

Jianping Li, Ying Yin, 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 algorithm; maximum traveling salesman problem; parameterized triangle inequality

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68W25: Approximation algorithms

Related Items

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