An improved approximation algorithm for the maximum TSP

DOI10.1016/J.TCS.2010.03.012MaRDI QIDQ974748zbMATH OpenOpenAlexFDO

Authors Tongquan Zhang, Ying Yin, Jianping Li

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

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

Recommendations

• On the maximum TSP with -parameterized triangle inequality
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Improved deterministic approximation algorithms for max TSP
• scientific article; zbMATH DE number 2038707
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

Cites work

• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• An -approximation algorithm for the asymmetric maximum TSP
• An approximation algorithm for the maximum traveling salesman problem
• An exact -constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Deterministic 7/8-approximation for the metric maximum TSP
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the relationship between ATSP and the cycle cover problem
• On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem

Cited in

(18)

• Deterministic 7/8-approximation for the metric maximum TSP
• Improving the robustness of EPS to solve the TSP
• Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
• An improved exact algorithm for TSP in graphs of maximum degree 4
• scientific article; zbMATH DE number 5952642 (Why is no real title available?)
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Approximating Multi-criteria Max-TSP
• Maximum Scatter TSP in Doubling Metrics
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Improved Approximation Lower Bounds for TSP with Distances One and Two
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• An improved approximation algorithm for ATSP
• An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
• Approximating TSP Solution by MST Based Graph Pyramid
• THE TSP AND THE SUM OF ITS MARGINAL VALUES
• On the maximum TSP with -parameterized triangle inequality
• Deterministic algorithms for multi-criteria max-TSP
• On the maximum betweenness improvement problem

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

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