On patching algorithms for random asymmetric travelling salesman problems (Q1813831)

Let the arc-lengths \(\ell_{ij}\) of a complete digraph of order \(n\) be independent uniform \([0,1]\) random variables. The authors consider the patching algorithm of \textit{R. M. Karp} [SIAM J. Comput. 8, 561-573 (1979; Zbl 0427.90064)] and \textit{R. M. Karp} and \textit{J. M. Steele} [in: The travelling salesman problem, a guided tour of combinatorial optimization, 181-205 (1985; Zbl 0582.90100)] for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. These ideas are also extended to the \(k\)-person travelling salesman problem [see \textit{G. Frederickson, M. Hecht} and \textit{C. Kim}, SIAM J. Comput. 7, 178-193 (1978)] and the problem of finding the minimum length closed walk through the vertex set of the digraph.