Today I read a paper titled “The Symmetric Traveling Salesman Problem”
The abstract is:
Let M be an nXn symetric matrix, n, even, T, an upper bound for T_OPT, an optimal tour, sigma_T, the smaller-valued perfect matching obtained from alternate edges of T expressed as a product of 2-cycles.
Applying the modified Floyd-Warshall algorithm to (sigma_T)^-1M^-, we construct acceptable and 2-circuit cycles some sets of which may yield circuits that can be patched into tours.
We obtain necessary and sufficient conditions for a set, S, of cycles to yield circuits that may be patched into a tour.Assume that the following (Condition A)is valid: If (sigma_T)s = T*, |T*|
Given Condition(A), using F-W, we can always obtain S(FWOPT).
Using Condition A but not F-W, S_OPT is always obtainable from a subset of the cycles obtained.