Enviar artigo por via de e-mail A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
- Autores: Glebov A.1,2, Toktokhoeva S.2
-
Afiliações:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Edição: Volume 13, Nº 2 (2019)
- Páginas: 219-238
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213165
- DOI: https://doi.org/10.1134/S1990478919020042
- ID: 213165
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Sobre autores
A. Glebov
Sobolev Institute of Mathematics; Novosibirsk State University
Autor responsável pela correspondência
Email: angle@math.nsc.ru
Rússia, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 1, Novosibirsk, 630090
S. Toktokhoeva
Novosibirsk State University
Autor responsável pela correspondência
Email: s.toktokhoeva@ya.ru
Rússia, ul. Pirogova 1, Novosibirsk, 630090
