Given n cities and a distance matrix, the traveling salesman problem (TSP) is to find a closed directed tour (passing all cities) with minimum total length. The TSP is a well-known NP-complete problem. Therefore, its approximate algorithms attract many studies. When the distance matrix C satisfies the triangle inequality, there is a bounded heuristic within the factor of 1.5$\cdot S(C)$ from optimal, where S(C) is called the degree of asymmetry of $C=(c\sb{ij})$ and is defined to be $+\infty$ if there is a pair i, j such that $sign(c\sb{ij})\ne sign(c\sb{ji})$, and $\max \{c\sb{ij}/c\sb{ji}:$ $c\sb{ji}\ne 0\}$ otherwise. For a vector u, define $C(u)=(c\sb{ij}-u\sb i+u\sb j)$. In this paper, an algorithm is presented to find u such that S(C(u)) achieves a minimum. The authors also introduce a new degree of asymmetry and study the relationship between two degrees of asymmetry.
Reviewer: D.-Z.Du