Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem

Triangle inequality and symmetry play an important role in the treatment of the traveling salesman problem (TSP). Examplarily it is shown how to transform the distance matrix in order to use a given heuristic algorithm; furthermore related performance bounds will be given and studied. The corresponding transformation originates in the dual assignment problem. Finally results concerning the exact case are mentioned as reducing the dimension of the original TSP and as well as the restricted use of non-optimal edges. The paper represents a survey of the above mentioned topic.