## CLASS-L@LISTS.SUNYSB.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Monospaced Font

Subject:

Re: reordering matrices

From:

Classification, clustering, and phylogeny estimation

Date:

Wed, 29 Jun 2005 20:24:34 +0200

Content-Type:

text/plain

Parts/Attachments:

 text/plain (27 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... Pawel