An approximation algorithm for the maximum traveling salesman problem

DOI10.1016/S0020-0190(98)00102-1MaRDI QIDQ293334zbMATH OpenFDO

Authors Refael Hassin, Shlomi Rubinstein

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

zbMATH Keywords

analysis of algorithmsmaximum traveling salesman

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• An approximation algorithm for the maximum traveling salesman problem
• Better approximations for max TSP
• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• Improved deterministic approximation algorithms for max TSP
• Algorithms – ESA 2005

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• An Analysis of the Greedy Heuristic for Independence Systems
• 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
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(25)

• Improved deterministic approximation algorithms for max TSP
• scientific article; zbMATH DE number 1534500 (Why is no real title available?)
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A certain generalization of the maximum traveling salesman problem
• On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• scientific article; zbMATH DE number 3910163 (Why is no real title available?)
• An improved randomized approximation algorithm for Max TSP
• THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES
• scientific article; zbMATH DE number 2080248 (Why is no real title available?)
• The maximum resource bin packing problem
• Better Approximation Algorithms for Scaffolding Problems
• Better approximations for max TSP
• An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
• An approximation algorithm for the maximum traveling salesman problem
• On the approximability of the traveling salesman problem
• Approximation algorithms for the scaffolding problem and its generalizations
• The lazy bureaucrat scheduling problem
• An improved approximation algorithm for the maximum TSP
• On lazy bureaucrat scheduling with common deadlines
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• scientific article; zbMATH DE number 808804 (Why is no real title available?)
• scientific article; zbMATH DE number 598850 (Why is no real title available?)
• scientific article; zbMATH DE number 6007868 (Why is no real title available?)

This page was built for publication: An approximation algorithm for the maximum traveling salesman problem

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