RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






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


Trudy Inst. Mat. i Mekh. UrO RAN, 2010, Volume 16, Number 3, Pages 12–24 (Mi timm572)  

This article is cited in 10 scientific papers (total in 10 papers)

On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space

A. E. Baburin, E. Kh. Gimadia

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: An efficient algorithm $\mathcal A$ with a guaranteed accuracy estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman routes) of maximal weight in a complete weighted undirected graph in a multidimensional Euclidean space $\mathbb R^k$. The complexity of the algorithm is $O(n^3)$. The number of traveling salesman routes for which the algorithm is asymptotically exact is established.

Keywords: maximum traveling salesman problem, edge-disjoint Hamiltonian circuits, polynomial algorithm, asymptotic accuracy, multidimensional Euclidean space.

Full text: PDF file (220 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2011, 272, suppl. 1, S1–S13

Bibliographic databases:

UDC: 519.8
Received: 31.03.2010

Citation: 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”, Trudy Inst. Mat. i Mekh. UrO RAN, 16, no. 3, 2010, 12–24; Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S1–S13

Citation in format AMSBIB
\Bibitem{BabGim10}
\by A.~E.~Baburin, E.~Kh.~Gimadi
\paper On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a~multidimensional Euclidean space
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2010
\vol 16
\issue 3
\pages 12--24
\mathnet{http://mi.mathnet.ru/timm572}
\elib{http://elibrary.ru/item.asp?id=15173460}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2011
\vol 272
\issue , suppl. 1
\pages S1--S13
\crossref{https://doi.org/10.1134/S0081543811020015}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000289527400001}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79954620627}


Linking options:
  • http://mi.mathnet.ru/eng/timm572
  • http://mi.mathnet.ru/eng/timm/v16/i3/p12

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. E. Duchenne, G. Laporte, F. Semet, “The Undirected M-Capacitated Peripatetic Salesman Problem”, Eur. J. Oper. Res., 223:3 (2012), 637–643  crossref  mathscinet  zmath  isi  elib  scopus
    2. E. Kh. Gimadi, Yu. V. Glazkov, O. Yu. Tsidulko, “The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations”, J. Appl. Industr. Math., 8:2 (2014), 208–217  mathnet  crossref  mathscinet  isi
    3. E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, “Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 77–87  mathnet  crossref  mathscinet  isi  elib
    4. E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  mathnet  crossref  mathscinet  isi  elib
    5. V. V. Shenmaier, “Asymptotically Optimal Algorithms for Geometric Max TSP and Max M-PSP”, Discrete Appl. Math., 163:2, SI (2014), 214–219  crossref  mathscinet  zmath  isi  elib  scopus
    6. 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, suppl. 1 (2015), 111–125  mathnet  crossref  mathscinet  isi  elib
    7. 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  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    8. E. Kh. Gimadi, O. Yu. Tsidulko, “An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution”, J. Appl. Industr. Math., 11:3 (2017), 354–361  mathnet  crossref  crossref  elib
    9. E. Kh. Gimadi, O. Yu. Tsidulko, “Approximation Algorithms For the Maximum M-Peripatetic Salesman Problem”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. Van Der Aalst W., Ignatov D., Khachay M., Kuznetsov S., Lempitsky V., Lomazova I., Loukachevitch N.,, Springer International Publishing Ag, 2018, 304–312  crossref  isi  scopus
    10. 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  mathnet  crossref  crossref
  • Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Number of views:
    This page:318
    Full text:86
    References:35

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020