|
Diskretnyi Analiz i Issledovanie Operatsii, 2011, Volume 18, Issue 4, Pages 17–48
(Mi da658)
|
|
|
|
This article is cited in 16 scientific papers (total in 16 papers)
Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP
A. N. Glebovab, D. Zh. Zambalayevaa a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Abstract:
We study a 2-peripatetic salesman problem on maximum which consists in finding two edge-disjoint Hamiltonian cycles of maximum total weight in a complete undirected graph. We present a cubic time approximation algorithm for this problem with guaranteed ratio $7/9$, the best known for today. Ill. 5, bibliogr. 14.
Keywords:
traveling salesman problem, 2-peripatetic salesman problem, polynomial algorithm, guaranteed approximation ratio.
Received: 25.01.2011 Revised: 06.05.2011
Citation:
A. N. Glebov, D. Zh. Zambalayeva, “Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP”, Diskretn. Anal. Issled. Oper., 18:4 (2011), 17–48; J. Appl. Industr. Math., 6:1 (2012), 69–89
Linking options:
https://www.mathnet.ru/eng/da658 https://www.mathnet.ru/eng/da/v18/i4/p17
|
Statistics & downloads: |
Abstract page: | 522 | Full-text PDF : | 88 | References: | 48 | First page: | 5 |
|