Several polynomial time approximation algorithms for some $NP$-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the stacker-crane problem (a modified traveling salesman problem). A tour-splitting heuristic is given for k-person variants of the traveling salesman problem, the Chinese postman problem, and the stacker-crane problem, for which a minimax solution is sought. This heuristic has a bound of $e + 1 - 1/k$, where e is the bound for the corresponding 1-person algorithm.
['Greg N. Frederickson', 'Matthew S. Hecht', 'Chul E. Kim']
Approximation Algorithms for Some Routing Problems