电邮这篇文章 A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
- 作者: Glebov A.N.1,2, Toktokhoeva S.G.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
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
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
补充文件
