Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem

For the distance matrix of symmetric traveling salesman problems a simple transformation into an equivalent asymmetric one is given. Assignment algorithms yield sharper lowerbounds and less subtours from the transformed distance matrix. This implies a better performance for traveling salesman algorithms based on the assignment relaxation.