Zu verschärfungen der christofibes-schranke fü den wert einer optimalen tour des enndrelseproblems

Abstract

A necessary and sufficient condition for a distance matrix which can be reduced to a matrix with fulfilled triangle inequality is presented. If the reduced matrix fulfills the triangle inequality then the dimension of the original traveling salesman problem can be at least halved.

By using a method presented in this paper it is possible to prove efficiently whether the optimal reduced matrix fulfills the triangle inequality. The number of operations is O(n ³).