×

zbMATH — the first resource for mathematics

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.

MSC:
90C35 Programming involving graphs or networks
90C10 Integer programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite