An improved approximation algorithm for the maximum TSP
From MaRDI portal
Publication:974748
DOI10.1016/J.TCS.2010.03.012zbMATH Open1203.68318OpenAlexW1982624404MaRDI QIDQ974748FDOQ974748
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
Recommendations
- On the maximum TSP with \(\gamma\)-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
- Title not available (Why is that?)
- 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
- An approximation algorithm for the maximum traveling salesman problem
- On the relationship between ATSP and the cycle cover problem
- Deterministic 7/8-approximation for the metric maximum TSP
- An -approximation algorithm for the asymmetric maximum TSP
- Differential approximation results for the traveling salesman problem with distances 1 and 2
- On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
- An improved approximation algorithm for the ATSP with parameterized triangle inequality
Cited In (17)
- Title not available (Why is that?)
- An improved exact algorithm for TSP in graphs of maximum degree 4
- Deterministic 7/8-approximation for the metric maximum TSP
- On the maximum TSP with \(\gamma\)-parameterized triangle inequality
- An improved approximation algorithm for ATSP
- Maximum Scatter TSP in Doubling Metrics
- On the maximum betweenness improvement problem
- THE TSP AND THE SUM OF ITS MARGINAL VALUES
- Improving the robustness of EPS to solve the TSP
- Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions
- Approximating TSP Solution by MST Based Graph Pyramid
- An improved approximation algorithm for the ATSP with parameterized triangle inequality
- Improved Approximation Lower Bounds for TSP with Distances One and Two
- Approximating Multi-criteria Max-TSP
- Deterministic algorithms for multi-criteria max-TSP
- An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
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)
