Premium
On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem
Author(s) -
Frieze A. M.,
Galbiati G.,
Maffioli F.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120103
Subject(s) - travelling salesman problem , heuristics , heuristic , mathematics , mathematical optimization , traveling purchaser problem , computer science , construct (python library) , algorithm , bottleneck traveling salesman problem , combinatorics , programming language
We consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst‐case ratio of length of tour found to minimum length tour is ( n ) for n city problems. We also provide a new O ([log 2 n ]) heuristic.