The Symmetric Traveling Salesman Problem
| dc.creator | Kleiman, Howard | |
| dc.date | 2005-08-11 | |
| dc.date | 2005-08-27 | |
| dc.date.accessioned | 2026-07-07T05:22:19Z | |
| dc.date.available | 2026-07-07T05:22:19Z | |
| dc.description | 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. | |
| dc.description | A new theorem has been added | |
| dc.identifier | https://arxiv.org/abs/math/0508212 | |
| dc.identifier | http://arxiv.org/abs/math/0508212 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76014 | |
| dc.subject | Combinatorics | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | 05 | |
| dc.title | The Symmetric Traveling Salesman Problem | |
| dc.type | text |