Volume 18, No 4, 2011, P. 17-48
A. N. Glebov, D. Zh. Zambalaeva
Polynomial algorithm with approximation ratio 7/9 for maximum 2-psp
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
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: firstname.lastname@example.org, email@example.com