%0 Generic %1 citeulike:992534 %A Kleiman, Howard %D 2005 %K problem salesman symmetric traveling %T The Symmetric Traveling Salesman Problem %U http://arxiv.org/abs/math.CO/0508212 %X 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*|<T, then all cycles of s have values less than |T| - |sigma_T|.Let SFWOPT),S(OPT)be the respective sets of cycles yielding T_FWOPT, T_OPT. 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.

@misc{citeulike:992534, abstract = {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*|\<T, then all cycles of s have values less than |T| - |sigma_T|.Let SFWOPT),S(OPT)be the respective sets of cycles yielding T_FWOPT, T_OPT. 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.}, added-at = {2007-08-18T13:22:24.000+0200}, author = {Kleiman, Howard}, biburl = {https://www.bibsonomy.org/bibtex/21b9d79fdcdf3a3861f3ff02346aa9530/a_olympia}, citeulike-article-id = {992534}, description = {citeulike}, eprint = {math.CO/0508212}, interhash = {ce728497402ec4250b8aee8319a29efb}, intrahash = {1b9d79fdcdf3a3861f3ff02346aa9530}, keywords = {problem salesman symmetric traveling}, month = Aug, priority = {2}, timestamp = {2007-08-18T13:22:32.000+0200}, title = {The Symmetric Traveling Salesman Problem}, url = {http://arxiv.org/abs/math.CO/0508212}, year = 2005 }