Email this article A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
- Authors: Glebov A.N.1,2, Toktokhoeva S.G.2
-
Affiliations:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Issue: Vol 13, No 2 (2019)
- Pages: 219-238
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213165
- DOI: https://doi.org/10.1134/S1990478919020042
- ID: 213165
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
A. N. Glebov
Sobolev Institute of Mathematics; Novosibirsk State University
Author for correspondence.
Email: angle@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 1, Novosibirsk, 630090
S. G. Toktokhoeva
Novosibirsk State University
Author for correspondence.
Email: s.toktokhoeva@ya.ru
Russian Federation, ul. Pirogova 1, Novosibirsk, 630090
Supplementary files
