A. N. Glebov, D. Zh. Zambalayeva, “An approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2”, Diskretn. Anal. Issled. Oper., 2011, Volume 18, Issue 5,Pages <nobr>11

This article is cited in 10 papers

An approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2

A. N. Glebov^ab, D. Zh. Zambalayeva^a

^a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
^b Novosibirsk State University, Novosibirsk, Russia

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

UDC: 519.8

Received: 23.06.2011