Your problem seems to be formulated as the maximum weight bipartite matching and the assignment problem.
You are looking to assign n rows to n columns at the greatest total cost.
This problem can be solved by the popular Hungariantype O(n3) algorithm.
Many references are available one the net.
Ref : H. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Q., 2:8397, 1955.
Gilles
Pr. Gilles Caraux
Agro Montpellier / LIRMM
France
Le 20:17 29/06/2005, vous avez écrit:
>Let me restate the problem  I am thinking there is an easier problem
>then what I have been receiving  though thank you for those.
>
>We have two dendrograms on the same objects and want to find stopping
>rules to cut each such thazt the overlap in the partitions is maxium. My
>thought (which may make this a more complicated problem) was to generate a
>contingency table of the two partitions and reorder the table to put the
>largest intersection counts on the diagonal.
>
>
>Is there a simpler rule to identify which clusters from the two tree have
>maximum overlap?
>
>Thanks
>
>
>Bill
>
>
> Biostatistics Consulting Center
> http://ilya.wustl.edu/~shannon/bcc_announcement.pdf
>
>
>William D. Shannon, Ph.D.
>
>Associate Professor of Biostatistics in Medicine
>Division of General Medical Sciences and Biostatistics
>
>Washington University School of Medicine
>Campus Box 8005, 660 S. Euclid
>St. Louis, MO 63110
>
>Phone: 3144548356
>Fax: 3144545113
>email: [log in to unmask]
>web page: http://ilya.wustl.edu/~shannon
>
>
>On Wed, 29 Jun 2005, Michael Brusco wrote:
>
>> This is a particular type of seriation problem for which optimal solutions
>> can typically be obtained for rather large problems. Depending on computer
>> RAM, Dynamic programming can provide an optimal solution for problems up to
>> about 25x25 (512MB or RAM). Branchandbound can provide guaranteed
>> optimal solutions for even larger problems and is not encumbered by memory
>> limitations. However, the branchandbound approach is more sensitive to
>> the data entries in the matrix and can require more CPU time. I've also
>> been able to solve some rather large problems using integer
>> programming. There are a number of references that focus on seriation
>> problems related to the dominance index you've mentioned, antiRobinson
>> gradient indices, and leastsquares unidimensional scaling. All of these
>> are amenable to optimal solution via branchandbound or dynamic
>> programming. I can send you some fortran programs if you like.
>>
>> Citations:
>> Hubert, Arabie, & Meulman (2001), Combinatorial Data Analysis:
>> Optimization by Dynamic Programming, SIAM.
>> Brusco & Stahl (in press), BranchandBound Applications in Combinatorial
>> Data Analysis, Springer.
>> Hubert & Golledge (1981), Psychometrika  dynamic programming
>> Brusco & Stahl (2001), Psychometrika, pp. 524  dynamic programming
>> Brusco (2002) Psychometrika, pp. 459471  branch and bound (antiRobinson
>> gradients)
>>
>> Mike
>>
>> At 06:53 PM 6/29/2005 +0200, you wrote:
>> >If your matrix can be reorganize as an Robinson matrix, you have a lot of
>> >good algorithms as I described in the manual of PermutMatrix, a software
>> >for seriation and clustering (http://www.lirmm.fr/~caraux/PermutMatrix/).
>> >I also give some references.
>> >For the general case, I think you have to perform every reordering if you
>> >want an exact solution.
>> >
>> >Gilles
>> >
>> >
>> >Le 18:18 29/06/2005, vous avez écrit:
>> > >Mighty mathematicians we have a question.
>> > >
>> > >We have small matrices of integers that we need to reorder so that the sum
>> > >of the diagonal is maximum.
>> > >
>> > >These matrices are relatively small (say 10x10 max) so we can brute force
>> > >our way by performing every reordering, but would rather not.
>> > >
>> > >Can anyone help we biostatisticians with an algorithm or theorem?
>> > >
>> > >
>> > >Bill
>> > >
>> > >
>> > > Biostatistics Consulting Center
>> > > http://ilya.wustl.edu/~shannon/bcc_announcement.pdf
>> > >
>> > >
>> > >William D. Shannon, Ph.D.
>> > >
>> > >Associate Professor of Biostatistics in Medicine
>> > >Division of General Medical Sciences and Biostatistics
>> > >
>> > >Washington University School of Medicine
>> > >Campus Box 8005, 660 S. Euclid
>> > >St. Louis, MO 63110
>> > >
>> > >Phone: 3144548356
>> > >Fax: 3144545113
>> > >email: [log in to unmask]
>> > >web page: http://ilya.wustl.edu/~shannon
>>
>> Michael J. Brusco, Marketing Department, College of Business, Florida State
>> University, Tallahassee, FL 323061110. Voice: (850)6446512, FAX:
>> (850)6444098, email: [log in to unmask]
>>
