Volume 18, No 5, 2011, P. 11-37
A. N. Glebov, D. Zh. Zambalaeva
An approximation algorithm for the minimum 2-psp with different weight functions valued 1 and 2
We present a polynomial algorithm with time complexity O(n5) and approximation ratio 4/3 (plus some additive constant) for the 2-peripatetic salesman problem on minimum with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1,2)-min-2w). Our result improves the other known algorithm for this problem with approximation ratio 11/7.
Ill. 3, bibliogr. 10.
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