Volume 18, No 4, 2011, P. 17-48

UDC 519.8
A. N. Glebov, D. Zh. Zambalaeva
Polynomial algorithm with approximation ratio 7/9 for maximum 2-psp

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. 15.

Keywords: traveling salesman problem, 2-peripatetic salesman problem, polynomial algorithm, guaranteed approximation ratio.

Glebov Aleksey Nikolaevich ^1,2
Zambalaeva Dolgor Zhamyanovna ¹
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
e-mail: angle@math.nsc.ru, dolgor@ngs.ru