On patching algorithms for random asymmetric travelling salesman problems

Let the arc-lengths Lij of a complete digraph on n vertices be independent uniform [0,1] random variables. The authors consider the patching algorithm of Karp and Steele for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. They extend these ideas to the k-person travelling salesman problem and also consider the case where cities can be visited more than once.