Small and large TSP: Two polynomially solvable cases of the traveling salesman problem

The problem of minimizing and maximizing the objective function of the Traveling Salesman Problem (TSP) is discussed. In particular, the authors consider two special cases of the TSP, namely the small TSP and the large TSP, for which both a minimum and a maximum of the objective function can be obtained in polynomial time. The cost matrix C=(cij) corresponding to the small (large) TSP is defined by cij=min{ai,bj}(cij=max{ai,bj}) for each i,j=1,...,n and n-dimensional real vectors a and b. The main purpose of this paper is to show the relationship between the subtour elimination algorithm of Gilmore and Gomory for the large TSP, and Gabovich’s algorithm for the small TSP. The recognition problem for these two types of matrices is solved by using Deineko and Filonenko’s algorithm for recognizing permuted distribution matrices. Finally, as an application, a problem from machine scheduling theory is considered.