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 Hungarian-type 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:83--97, 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: 314-454-8356
>Fax: 314-454-5113
>e-mail: [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). Branch-and-bound can provide guaranteed
>> optimal solutions for even larger problems and is not encumbered by memory
>> limitations. However, the branch-and-bound 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, anti-Robinson
>> gradient indices, and least-squares unidimensional scaling. All of these
>> are amenable to optimal solution via branch-and-bound 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), Branch-and-Bound Applications in Combinatorial
>> Data Analysis, Springer.
>> Hubert & Golledge (1981), Psychometrika - dynamic programming
>> Brusco & Stahl (2001), Psychometrika, pp. 5-24 - dynamic programming
>> Brusco (2002) Psychometrika, pp. 459-471 - branch and bound (anti-Robinson
>> 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: 314-454-8356
>> > >Fax: 314-454-5113
>> > >e-mail: [log in to unmask]
>> > >web page: http://ilya.wustl.edu/~shannon
>>
>> Michael J. Brusco, Marketing Department, College of Business, Florida State
>> University, Tallahassee, FL 32306-1110. Voice: (850)644-6512, FAX:
>> (850)644-4098, email: [log in to unmask]
>>
|
