Journal of Computational and Engineering Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



J. Comp. Eng. Math.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Journal of Computational and Engineering Mathematics, 2017, Volume 4, Issue 3, Pages 49–54
DOI: https://doi.org/10.14529/jcem170306
(Mi jcem99)
 

Short Notes

An approximation algorithm for the maximum traveling salesman problem

A. Yu. Evnin, N. I. Yusova

South Ural State University, Chelyabinsk, Russian Federation
References:
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
Bibliographic databases:
Document Type: Article
UDC: 519.161
MSC: 05C85
Language: English
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
Citation in format AMSBIB
\Bibitem{EvnYus17}
\by A.~Yu.~Evnin, N.~I.~Yusova
\paper An approximation algorithm for the maximum traveling salesman problem
\jour J. Comp. Eng. Math.
\yr 2017
\vol 4
\issue 3
\pages 49--54
\mathnet{http://mi.mathnet.ru/jcem99}
\crossref{https://doi.org/10.14529/jcem170306}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3708704}
\elib{https://elibrary.ru/item.asp?id=30289927}
Linking options:
  • https://www.mathnet.ru/eng/jcem99
  • https://www.mathnet.ru/eng/jcem/v4/i3/p49
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Journal of Computational and Engineering Mathematics
    Statistics & downloads:
    Abstract page:183
    Full-text PDF :88
    References:46
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024