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

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

Journal

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Output data

Year: 2019, Volume: 13, Number: 2, Pages: 219-238 Pages count : 20 DOI: 10.1134/S1990478919020042

Tags

approximation algorithm; guaranteed approximation ratio; Hamiltonian cycle; m-peripatetic salesman problem; traveling salesman problem

Authors

Glebov A.N. ^1,2 , Toktokhoeva S.G. ²

Affiliations

1	Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090, Russian Federation

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. © 2019, Pleiades Publishing, Ltd.

Glebov A.N. , Toktokhoeva S.G.
A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Journal of Applied and Industrial Mathematics. 2019. V.13. N2. P.219-238. DOI: 10.1134/S1990478919020042 Scopus OpenAlex

Глебов А.Н. , Токтохоева С.Г.
Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2019. Т.26. №2. С.30-59.

Scopus:	2-s2.0-85067404465
OpenAlex:	W2952489944

DB	Citing
Scopus	1
OpenAlex	1