Volume 18, No 4, 2011, P. 1748
UDC 519.8
A. N. Glebov, D. Zh. Zambalaeva
Polynomial algorithm with approximation ratio 7/9 for maximum 2psp
Abstract:
We study a 2peripatetic salesman problem on maximum which consists in finding two edgedisjoint 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. 15.
Keywords: traveling salesman problem, 2peripatetic salesman problem, polynomial algorithm, guaranteed approximation ratio.
Glebov Aleksey Nikolaevich ^{1,2}
Zambalaeva Dolgor Zhamyanovna ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
email: angle@math.nsc.ru, dolgor@ngs.ru
