A. N. Glebov, A. V. Gordeeva, D. Zh. Zambalayeva, “7/5-approximation algorithm for 2-PSP on minimum with different weight functions”, Sib. Èlektron. Mat. Izv., 2011, Volume 8,Pages <nobr>296

This article is cited in 5 papers

7/5-approximation algorithm for 2-PSP on minimum with different weight functions

A. N. Glebov^a, A. V. Gordeeva^b, D. Zh. Zambalayeva^a

^a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
^b Novosibirsk State University

Abstract: We present a cubic time algorithm with approximation ratio 7/5 (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 which has approximation ratio 11/7.

Keywords: Traveling Salesman Problem, 2-Peripatetic Salesman Problem, polynomial algorithm, guaranteed approximation ratio.

UDC: 519.712.3

MSC: 68W25

Received August 29, 2011, published October 11, 2011