SMALL AND LARGE TSP - 2 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, we cons ider 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 = (c(ij)) corres ponding to the small (large) TSP is defined by c(ij) = min{a(i), b(j)} (c(ij) = max(a(i), b(j)}) for each i, j = 1, ..., n and n-dimensional real vectors a and b. The main purpose of this paper is to show the r elationship between the subtour elimination algorithm of Gilmore and G omory for the large TSP, and Gabovich's algorithm for the small TSP. T he recognition problem for these two types,of matrices is solved by us ing Deineko and Filonenko's algorithm for recognizing permuted distrib ution matrices. Finally, as an application, a problem from machine sch eduling theory is considered.