Standard

A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP. / Glebov, A. N.; Toktokhoeva, S. G.

In: Journal of Applied and Industrial Mathematics, Vol. 14, No. 3, 01.08.2020, p. 456-469.

Research output: Contribution to journal › Article › peer-review

Harvard

Glebov, AN & Toktokhoeva, SG 2020, 'A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP', Journal of Applied and Industrial Mathematics, vol. 14, no. 3, pp. 456-469. https://doi.org/10.1134/S1990478920030059

APA

Glebov, A. N., & Toktokhoeva, S. G. (2020). A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP. Journal of Applied and Industrial Mathematics, 14(3), 456-469. https://doi.org/10.1134/S1990478920030059

Vancouver

Glebov AN, Toktokhoeva SG. A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP. Journal of Applied and Industrial Mathematics. 2020 Aug 1;14(3):456-469. doi: 10.1134/S1990478920030059

Author

Glebov, A. N. ; Toktokhoeva, S. G. / A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP. In: Journal of Applied and Industrial Mathematics. 2020 ; Vol. 14, No. 3. pp. 456-469.

BibTeX

@article{7cdfe479314f405e901c23a52524fe73,
title = "A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP",
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).",
keywords = "approximation algorithm, guaranteed approximation ratio, Hamiltonian cycle, m-Peripatetic Salesman Problem, Traveling Salesman Problem",
author = "Glebov, {A. N.} and Toktokhoeva, {S. G.}",
year = "2020",
month = aug,
day = "1",
doi = "10.1134/S1990478920030059",
language = "English",
volume = "14",
pages = "456--469",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "3",

}

RIS

TY - JOUR

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

AU - Glebov, A. N.

AU - Toktokhoeva, S. G.

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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).

AB - 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).

KW - approximation algorithm

KW - guaranteed approximation ratio

KW - Hamiltonian cycle

KW - m-Peripatetic Salesman Problem

KW - Traveling Salesman Problem

UR - http://www.scopus.com/inward/record.url?scp=85094634807&partnerID=8YFLogxK

U2 - 10.1134/S1990478920030059

DO - 10.1134/S1990478920030059

M3 - Article

AN - SCOPUS:85094634807

VL - 14

SP - 456

EP - 469

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 3

ER -

ID: 25851054