On the degree of asymmetry in the travelling salesman problem. (English) Zbl 0637.90096

Summary: The distance matrix of the travelling salesman problem is changed by suitable equivalence transformations in such a way that it becomes pseudosymmetric. This fact is exploited algorithmically in order to obtain “good” approximation tours for the asymmetric travelling salesman problem. A simple example shows that the given bounds are tight.


90C35 Programming involving graphs or networks
90C10 Integer programming
65K05 Numerical mathematical programming methods