Мақаланы E-mail арқылы жіберу A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
- Авторлар: Glebov A.1,2, Toktokhoeva S.2
-
Мекемелер:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Шығарылым: Том 13, № 2 (2019)
- Беттер: 219-238
- Бөлім: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213165
- DOI: https://doi.org/10.1134/S1990478919020042
- ID: 213165
Дәйексөз келтіру
Ашық рұқсат
Рұқсат берілді
Тек жазылушылар үшін
Аннотация
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.
Авторлар туралы
A. Glebov
Sobolev Institute of Mathematics; Novosibirsk State University
Хат алмасуға жауапты Автор.
Email: angle@math.nsc.ru
Ресей, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 1, Novosibirsk, 630090
S. Toktokhoeva
Novosibirsk State University
Хат алмасуға жауапты Автор.
Email: s.toktokhoeva@ya.ru
Ресей, ul. Pirogova 1, Novosibirsk, 630090
