Sciact
  • EN
  • RU

A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP Full article

Journal Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797
Output data Year: 2020, Volume: 14, Number: 3, Pages: 456-469 Pages count : 14 DOI: 10.1134/S1990478920030059
Tags approximation algorithm; guaranteed approximation ratio; Hamiltonian cycle; m-Peripatetic Salesman Problem; Traveling Salesman Problem
Authors Glebov A.N. 1,2 , Toktokhoeva S.G. 2
Affiliations
1 Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation
2 Novosibirsk State University, Novosibirsk, 630090, Russian Federation

Abstract: Abstract: In 2005, Kaplan et al. presented a polynomial-time algorithm with guaranteedapproximation ratio 2/3 for themaximization version of the asymmetric TSP. In 2014, Glebov, Skretneva, and Zambalaevaconstructed a similar algorithm with approximation ratio 2/3 and cubic runtime for the maximization version ofthe asymmetric 2-PSP (2-APSP-max), where it is required to find twoedge-disjoint Hamiltonian cycles of maximum total weight in a complete directed weighted graph.The goal of this paper is to construct a similar algorithm for the more general m-APSP-max in the asymmetric case and justify anapproximation ratio for this algorithm that tends to 2/3 as n grows and theruntime complexity estimate O(mn3). © 2020, Pleiades Publishing, Ltd.
Cite: Glebov A.N. , Toktokhoeva S.G.
A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP
Journal of Applied and Industrial Mathematics. 2020. V.14. N3. P.456-469. DOI: 10.1134/S1990478920030059 Scopus OpenAlex
Original: Глебов А.Н. , Токтохоева С.Г.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2020. Т.27. №3. С.28–52.
Identifiers:
Scopus: 2-s2.0-85094634807
OpenAlex: W3095646251
Citing:
DB Citing
Scopus 1
Altmetrics: