Derangements in Symmetric Cost Matrices

Details Derangements in Symmetric Cost Matrices Derangements in Symmetric Cost Matrices

2005-09-22

arxiv.org/abs/math/0509531v2

Mathematics

Combinatorics

In theorem 2, omitted conditions for preventing a path from containing a negative cycle

Scientific paper

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|.

Affiliated with

Also associated with

No associations

Rating

Derangements in Symmetric Cost Matrices 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 Derangements in Symmetric Cost Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Derangements in Symmetric Cost Matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-71180