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
"Pawel P. Baran" <[log in to unmask]>
Reply To:
Classification, clustering, and phylogeny estimation
Wed, 29 Jun 2005 20:24:34 +0200
text/plain (28 lines)
> 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

It's a rather simple dynamic programming issue (or I just did not understand
the problem); first you maximize the sum of the last two parameters on the
diagonal through all the pairs; then the sum of threes (where the last two
are properly ordered); next the sum of fours (where the last three are
ordered), and so on, up to 10 or what the number of rows is. Nice and pretty
easy algorithm called dynamic programming (backward) invented (or at least
first published) by Richard E. Bellman (R.E.Bellman, Dynamic Programming,
ca.1950; actually that's what he's famous for) close connected with adaptive
and optimal control. Last book worth mentioning is probably D. P. Bertsekas,
Dynamic Programming and Optimal Control, 2000. Any coursebook on Operations
Research/Management Science would probably be helpful.
BTW: for huge matrices this algorithm may not be fast enough though...