Disjoint Tours and the Price of Diversity

We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as possible. We investigate the Price of Diversity (PoD) for this problem, which is the ratio of the cost of the longer of the two tours and the cost of a single optimal tour, in the worst case over all possible instances. We prove (almost) tight bounds on this quantity for a special 1-dimensional scenario and for general metric spaces. We believe that the Price-of-Diversity framework that we introduce is interesting in its own right, and may lead to follow-up work on other problems as well.