|
Diskretnyi Analiz i Issledovanie Operatsii, 2014, Volume 21, Issue 6, Pages 11–20
(Mi da798)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
A. N. Glebov, D. Zh. Zambalaeva, A. A. Skretneva S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Abstract:
We present a polynomial approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem which consists in finding two edge-disjoint Hamiltonian circuits of maximum total weight in a complete weighted digraph. The algorithm guarantees an approximation ratio of $2/3$ in cubic running time. Ill. 5, bibliogr. 7.
Keywords:
traveling salesman problem, peripatetic salesman problem, polynomial algorithm, guaranteed ratio, directed graph.
Received: 02.12.2013 Revised: 11.07.2014
Citation:
A. N. Glebov, D. Zh. Zambalaeva, A. A. Skretneva, “$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem”, Diskretn. Anal. Issled. Oper., 21:6 (2014), 11–20; J. Appl. Industr. Math., 9:1 (2015), 61–67
Linking options:
https://www.mathnet.ru/eng/da798 https://www.mathnet.ru/eng/da/v21/i6/p11
|
Statistics & downloads: |
Abstract page: | 228 | Full-text PDF : | 195 | References: | 26 | First page: | 3 |
|