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.
No takes yet. Share an insight, caveat, or question.
Frieze et al. (1982) studied this question.