A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree Original Research Article

Suppose two travelling salesmen must visit together all points/nodes of a tree, and the objective is to minimize the maximal length of their tours. Home locations of the salesmen are given, and it is required to find optimal tours. For this NP-hard problem a heuristic with complexity O(n) is presented. The worst-case relative error for the heuristic performance is 13 for the case of equal home locations for both servers and 12 for the case of different home locations.