Standard

A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP. / Glebov, A. N.; Toktokhoeva, S. G.

In: Journal of Applied and Industrial Mathematics, Vol. 13, No. 2, 01.04.2019, p. 219-238.

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

Harvard

Glebov, AN & Toktokhoeva, SG 2019, 'A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP', Journal of Applied and Industrial Mathematics, vol. 13, no. 2, pp. 219-238. https://doi.org/10.1134/S1990478919020042

APA

Glebov, A. N., & Toktokhoeva, S. G. (2019). A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP. Journal of Applied and Industrial Mathematics, 13(2), 219-238. https://doi.org/10.1134/S1990478919020042

Vancouver

Glebov AN, Toktokhoeva SG. A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP. Journal of Applied and Industrial Mathematics. 2019 Apr 1;13(2):219-238. doi: 10.1134/S1990478919020042

Author

Glebov, A. N. ; Toktokhoeva, S. G. / A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP. In: Journal of Applied and Industrial Mathematics. 2019 ; Vol. 13, No. 2. pp. 219-238.

BibTeX

@article{c88c7ae3dc2c4459b58f5457b6eec055,
title = "A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP",
abstract = "We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric 3-Peripatetic Salesman Problem (3-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio 3/5 and cubic running-time.",
keywords = "approximation algorithm, guaranteed approximation ratio, Hamiltonian cycle, m-peripatetic salesman problem, traveling salesman problem",
author = "Glebov, {A. N.} and Toktokhoeva, {S. G.}",
year = "2019",
month = apr,
day = "1",
doi = "10.1134/S1990478919020042",
language = "English",
volume = "13",
pages = "219--238",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "2",

}

RIS

TY - JOUR

T1 - A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP

AU - Glebov, A. N.

AU - Toktokhoeva, S. G.

PY - 2019/4/1

Y1 - 2019/4/1

N2 - We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric 3-Peripatetic Salesman Problem (3-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio 3/5 and cubic running-time.

AB - We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric 3-Peripatetic Salesman Problem (3-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio 3/5 and cubic running-time.

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=85067404465&partnerID=8YFLogxK

U2 - 10.1134/S1990478919020042

DO - 10.1134/S1990478919020042

M3 - Article

AN - SCOPUS:85067404465

VL - 13

SP - 219

EP - 238

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -

ID: 20640524