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.