|
Short Notes
An approximation algorithm for the maximum traveling salesman problem
A. Yu. Evnin, N. I. Yusova South Ural State University, Chelyabinsk, Russian Federation
Abstract:
The question considered in the travelling salesman problem is the following. For a given list of cities and the distances between each pair of cities, to construct the shortest possible path that visits each city exactly once and returns to the origin city. The problem is an NP-hard problem in combinatorial optimization and is important in operations research. The traveling salesman problem is one of the most famous and heavily researched problems in theoretical computer science. We consider the version, which is the Symmetric Maximum Traveling Salesman Problem. The article describes an approximation algorithm for the maximum traveling salesman problem, based on two known polynomial time approximation algorithms. The accuracy of this algorithm is 25/33.
Keywords:
Hamiltonian cycle, traveling salesman problem, approximation algorithm, cycle cover, matching, accuracy of solution.
Received: 16.05.2017
Citation:
A. Yu. Evnin, N. I. Yusova, “An approximation algorithm for the maximum traveling salesman problem”, J. Comp. Eng. Math., 4:3 (2017), 49–54
Linking options:
https://www.mathnet.ru/eng/jcem99 https://www.mathnet.ru/eng/jcem/v4/i3/p49
|
Statistics & downloads: |
Abstract page: | 183 | Full-text PDF : | 88 | References: | 46 |
|