On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix
| dc.creator | Kleiman, Howard | |
| dc.date | 2005-09-20 | |
| dc.date.accessioned | 2026-07-07T06:18:20Z | |
| dc.date.available | 2026-07-07T06:18:20Z | |
| dc.description | Let M be an n X n symmetric cost matrix. Assume that D is a derangement of edges in M, i.e., a set of point-disjoint cycles containing all of the n points of M.The modified Floyd-Warshall algorithm applied to ((D')^-1)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 algorithm to D^-1)M^-, we may possibly obtain a smaller-valued derangement than D consisting of entries in M. A minimally-valued derangement would be of great value as a good and natural lower bound for an optimal tour in M. | |
| dc.description | It appears that this paper does not generally obtain what I hoped it would: A minimally-valued derangement of edges in a symmetric cost matrix.There may be another procedure that may do so but it has a greater running time | |
| dc.identifier | https://arxiv.org/abs/math/0509443 | |
| dc.identifier | http://arxiv.org/abs/math/0509443 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94702 | |
| dc.subject | Combinatorics | |
| dc.title | On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix | |
| dc.type | text |