Derangements in Symmetric Cost Matrices
| dc.creator | Kleiman, Howard | |
| dc.date | 2005-09-22 | |
| dc.date | 2005-09-27 | |
| dc.date.accessioned | 2026-07-07T06:19:40Z | |
| dc.date.available | 2026-07-07T06:19:40Z | |
| dc.description | Let M be an n X n symmetric cost matrix. Assume that D is a derangement in M, i.e.,a set of disjoint cycles consisting of edges that contains all of the n points of M. The modified Floyd-Warshall algorithm applied to (D')^-1(M^-)A^- (where A is an asymmetric cost matrix containing D', a derangement)yielded a solution to the Assignment Problem in O((n^2)logn) running time. Here, applying a variation of the modified F-W to (D^-1)M^-1, we can obtain D = D_FWABS, the smallest-valued derangement obtainable using the modified F-W. Let T_TSPOPT be an optimal tour in M. We give conditions for obtaining D_ABSOLUTE, the smallest-valued derangement obtainable in M, where |D_ABSOLUTE| <= |T_TSPOPT|. | |
| dc.description | In theorem 2, omitted conditions for preventing a path from containing a negative cycle | |
| dc.identifier | https://arxiv.org/abs/math/0509531 | |
| dc.identifier | http://arxiv.org/abs/math/0509531 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/95105 | |
| dc.subject | Combinatorics | |
| dc.subject | 05 | |
| dc.title | Derangements in Symmetric Cost Matrices | |
| dc.type | text |