Print

Print


> 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