Volume 18, No 5, 2011, P. 11-37

UDC 519.8
A. N. Glebov, D. Zh. Zambalaeva
An approximation algorithm for the minimum 2-psp with different weight functions valued 1 and 2

Abstract:
We present a polynomial algorithm with time complexity O(n⁵) 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. 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