On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix

Details On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix

2005-09-20

arxiv.org/abs/math/0509443v1

Mathematics

Combinatorics

It appears that this paper does not generally obtain what I hoped it would: A minimally-valued derangement of edges in a symme

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Obtaining a Minimally-Valued Derangement in a Symmetric Cost Matrix will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-1544