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