General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., Ser. 1, 2006, Volume 13, Number 2, Pages 11–20 (Mi da28)  

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

A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight

A. A. Ageev, A. E. Baburin, E. Kh. Gimadi

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

Abstract: We study the problem in which, given a complete undirected edge-weighted graph, it is required to find two (edge) disjoint Hamiltonian cycles of maximum total weight. The problem is known to be NP-hard in the strong sense. We present a 3/4-approximation algorithm with the running time $O(n^3)$.

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

English version:
Journal of Applied and Industrial Mathematics, 2007, 1:2, 142–147

Bibliographic databases:

Citation: A. A. Ageev, A. E. Baburin, E. Kh. Gimadi, “A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight”, Diskretn. Anal. Issled. Oper., Ser. 1, 13:2 (2006), 11–20; J. Appl. Industr. Math., 1:2 (2007), 142–147

Citation in format AMSBIB
\by A.~A.~Ageev, A.~E.~Baburin, E.~Kh.~Gimadi
\paper A polynomial algorithm with an accuracy estimate of~3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight
\jour Diskretn. Anal. Issled. Oper., Ser.~1
\yr 2006
\vol 13
\issue 2
\pages 11--20
\jour J. Appl. Industr. Math.
\yr 2007
\vol 1
\issue 2
\pages 142--147

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. J. Appl. Industr. Math., 3:1 (2009), 46–60  mathnet  crossref  zmath
    2. Ageev A.A., Pyatkin A.V., “A 2-approximation algorithm for the metric 2-peripatetic salesman problem”, Approximation and Online Algorithms, Lecture Notes in Computer Science, 4927, 2008, 103–115  crossref  mathscinet  zmath  isi  scopus
    3. A. A. Ageev, A. V. Pyatkin, “Priblizhennyi algoritm resheniya metricheskoi zadachi o dvukh kommivoyazherakh s otsenkoi tochnosti 2”, Diskretn. analiz i issled. oper., 16:4 (2009), 3–20  mathnet  mathscinet  zmath
    4. Baburin A.E., Della Croce F., Gimadi E.K., Glazkov Y.V., Paschos V.T., “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2”, Discrete Appl Math, 157:9 (2009), 1988–1992  crossref  mathscinet  zmath  isi  elib  scopus
    5. 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  mathnet  crossref  isi  elib
    6. A. N. Glebov, D. Zh. Zambalayeva, “Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP”, J. Appl. Industr. Math., 6:1 (2012), 69–89  mathnet  crossref  mathscinet  zmath
    7. A. N. Glebov, D. Zh. Zambalayeva, “An approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2”, J. Appl. Industr. Math., 6:2 (2012), 167–183  mathnet  crossref  mathscinet  zmath
    8. A. N. Glebov, A. V. Gordeeva, D. Zh. Zambalaeva, “Algoritm s otsenkoi 7/5 dlya zadachi o dvukh kommivoyazherakh na minimum s razlichnymi vesovymi funktsiyami”, Sib. elektron. matem. izv., 8 (2011), 296–309  mathnet
    9. E. Kh. Gimadi, E. V. Ivonina, “Approximation algorithms for maximum-weight problem of two-peripatetic salesmen”, J. Appl. Industr. Math., 6:3 (2012), 295–305  mathnet  crossref  mathscinet
    10. Duchenne E., Laporte G., Semet F., “The Undirected M-Capacitated Peripatetic Salesman Problem”, Eur. J. Oper. Res., 223:3 (2012), 637–643  crossref  mathscinet  zmath  isi  elib  scopus
    11. E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, “On $m$-capacitated peripatetic salesman problem”, J. Appl. Industr. Math., 8:1 (2014), 40–52  mathnet  crossref  mathscinet
    12. Shenmaier V.V., “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
    13. Michallet J., Prins Ch., Amodeo L., Yalaoui F., Vitry G., “Multi-Start Iterated Local Search for the Periodic Vehicle Routing Problem with Time Windows and Time Spread Constraints on Services”, Comput. Oper. Res., 41 (2014), 196–207  crossref  mathscinet  zmath  isi  elib  scopus
    14. E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, “Zadacha o dvukh kommivoyazherakh s ogranicheniyami na propusknye sposobnosti reber grafa s razlichnymi vesovymi funktsiyami”, Vestn. NGU. Ser. matem., mekh., inform., 14:3 (2014), 3–18  mathnet
    15. Gimadi E.Kh., Glebov A.N., Skretneva A.A., Tsidulko O.Yu., Zambalaeva D.Zh., “Combinatorial Algorithms With Performance Guarantees For Finding Several Hamiltonian Circuits in a Complete Directed Weighted Graph”, Discrete Appl. Math., 196:SI (2015), 54–61  crossref  mathscinet  zmath  isi  elib  scopus
    16. 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
    17. Gimadi E.Kh., Tsidulko O.Yu., “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. VanDerAalst W., Ignatov D., Khachay M., Kuznetsov S., Lempitsky V., Lomazova I., Loukachevitch N., Napoli A., Panchenko A., Pardalos P., Savchenko A., Wasserman S., Springer International Publishing Ag, 2018, 304–312  crossref  mathscinet  isi  scopus
    18. 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
  • Дискретный анализ и исследование операций
    Number of views:
    This page:506
    Full text:144

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