|
This article is cited in 2 scientific papers (total in 2 papers)
A polynomial $3/5$-approximate algorithm for the asymmetric maximization version of $3$-PSP
A. N. Glebovab, S. G. Toktokhoevab a Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia
b Novosibirsk State University, 1 Pirogov Street, 630090 Novosibirsk, Russia
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. Illustr. 18, bibliogr. 27.
Keywords:
Hamiltonian cycle, traveling salesman problem, $m$-peripatetic salesman problem, approximation algorithm, guaranteed approximation ratio.
Received: 06.06.2018 Revised: 27.11.2018 Accepted: 28.11.2018
Citation:
A. N. Glebov, S. G. Toktokhoeva, “A polynomial $3/5$-approximate algorithm for the asymmetric maximization version of $3$-PSP”, Diskretn. Anal. Issled. Oper., 26:2 (2019), 30–59; J. Appl. Industr. Math., 13:2 (2019), 219–238
Linking options:
https://www.mathnet.ru/eng/da922 https://www.mathnet.ru/eng/da/v26/i2/p30
|
Statistics & downloads: |
Abstract page: | 216 | Full-text PDF : | 57 | References: | 25 | First page: | 6 |
|