CLASS-L Archives

June 2005


Options: Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Michael Brusco <[log in to unmask]>
Reply To:
Classification, clustering, and phylogeny estimation
Wed, 29 Jun 2005 13:55:54 -0400
text/plain (74 lines)
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.

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


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 (
>I also give some references.
>For the general case, I think you have to perform every reordering if you
>want an exact solution.
>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
> >
> >
> >
> >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:

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]