Abstract:
The paper presents a polynomial approximation algorithm A solving the problem of finding one and
two edge-disjoint Hamiltonian cycles (traveling salesman routes) of maximal weight in a complete weighted
undirected graph in multidimensional Euclidean space. The asymptotic optimality of the algorithm is established.
Citation:
E. Kh. Gimadi, “Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space”, Trudy Inst. Mat. i Mekh. UrO RAN, 14, no. 2, 2008, 23–32; Proc. Steklov Inst. Math. (Suppl.), 263, suppl. 2 (2008), S57–S67
\Bibitem{Gim08}
\by E.~Kh.~Gimadi
\paper Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2008
\vol 14
\issue 2
\pages 23--32
\mathnet{http://mi.mathnet.ru/timm21}
\zmath{https://zbmath.org/?q=an:1178.90335}
\elib{https://elibrary.ru/item.asp?id=11929726}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2008
\vol 263
\issue , suppl. 2
\pages S57--S67
\crossref{https://doi.org/10.1134/S0081543808060072}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000208363700006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-60949091233}
Linking options:
https://www.mathnet.ru/eng/timm21
https://www.mathnet.ru/eng/timm/v14/i2/p23
This publication is cited in the following 11 articles:
A. N. Glebov, S. G. Toktokhoeva, “A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP”, J. Appl. Industr. Math., 14:3 (2020), 456–469
A. N. Glebov, S. G. Toktokhoeva, “A Polynomial Algorithm with Asymptotic Ratio
2/3 for the Asymmetric Maximization Version of
the m-PSP”, J. Appl. Ind. Math., 14:3 (2020), 456
A. N. Glebov, S. G. Toktokhoeva, “A polynomial 3/5-approximate algorithm for the asymmetric maximization version of 3-PSP”, J. Appl. Industr. Math., 13:2 (2019), 219–238
Edward Kh. Gimadi, Oxana Yu. Tsidulko, Lecture Notes in Computer Science, 11179, Analysis of Images, Social Networks and Texts, 2018, 283
Michael Khachay, Katherine Neznakhina, “Approximability of the minimum-weight k-size cycle cover problem”, J Glob Optim, 66:1 (2016), 65
Michael Khachay, Katherine Neznakhina, “Polynomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean space of an arbitrary fixed dimension”, IFAC-PapersOnLine, 49:12 (2016), 6
Aleksey N. Glebov, Anastasiya V. Gordeeva, Lecture Notes in Computer Science, 9869, Discrete Optimization and Operations Research, 2016, 159
Khachai M.Yu., Neznakhina E.D., “Approximability of the Problem About a Minimum-Weight Cycle Cover of a Graph”, Dokl. Math., 91:2 (2015), 240–245
M. Yu. Khachai, E. D. Neznakhina, “Polynomial-time approximation scheme for a Euclidean problem on a cycle covering of a graph”, Proc. Steklov Inst. Math. (Suppl.), 289:1 (2015), 111–125
E. E. Ivanko, “Method of scaling in approximate solution of the traveling salesman problem”, Autom. Remote Control, 72:12 (2011), 2527–2540
A. E. Baburin, E. Kh. Gimadi, “On the asymptotic accuracy of an algorithm for solving the m-PSP maximum problem in a multidimensional Euclidean space”, Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S1–S13
Citation in format AMSBIB
Contact us: