An approximation algorithm for the maximum traveling salesman problem
From MaRDI portal
Publication:293334
DOI10.1016/S0020-0190(98)00102-1zbMath1339.90282MaRDI QIDQ293334
Shlomi Rubinstein, Refael Hassin
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001021?np=y
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Approximation algorithms for the scaffolding problem and its generalizations ⋮ The lazy bureaucrat scheduling problem ⋮ On lazy bureaucrat scheduling with common deadlines ⋮ Better Approximation Algorithms for Scaffolding Problems ⋮ An improved approximation algorithm for the maximum TSP ⋮ The maximum resource bin packing problem ⋮ An Approximation Algorithm for the Maximum Traveling Salesman Problem ⋮ Improved deterministic approximation algorithms for max TSP ⋮ THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES ⋮ An improved randomized approximation algorithm for Max TSP ⋮ An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices ⋮ Better approximations for max TSP
Cites Work
- An approximation algorithm for maximum packing of 3-edge paths
- Maximizing traveling salesman problem for special matrices
- The maximum travelling salesman problem on symmetric Demidenko matrices
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An Analysis of the Greedy Heuristic for Independence Systems
- An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
- Two Algorithmic Results for the Traveling Salesman Problem
