Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: optimal sorting
Posted:
Dec 10, 2012 12:09 AM


nofingers wrote:
> > "gsgs" <sterten@aol.com> wrote in message > news:c2a74aef23b74a46ba7326926d10baea@googlegroups.com... >> given a (symmetrical) finite real square matrix d(n,n) >> find a permutation s in S_n such that >> >> SUM[i=2..n] ( min{d(s(i),s(j))0<j<i} ) is minimal >> >> how is it called, how to solve it >> > > what is s(i) ? or s(j) ? function, but what ?
A permutation of the indices { j  1<=j<=n }.
The question has to do with applying the same permutation to the row indices as the column indices, then performing a summation of minima, with the sum being over the row index and the minimum being over the column index, the sum and the min applying only to elements of the lower triangle of the posttransformation matrix.
That is, you are asked to minimize the sum of the columnwise mins of the resulting lower triangle.
I suppose you could think of s as the inverse of the indicial permutation, not the permutation itself. Calling the latter permutation t, and leaving out the parentheses in the function calls, could rewrite as
SUM[ t i >= 2 ] ( min( d(i,j)  t j < t i ) )
Note that the t i > 2 restriction is in a sense redundant, especially if you were to take the min of zero items to be zero.
It asks for an 'optimal sort' so I'll assume it is asking for an algorithm, and possibly an 'optimal' one at that. The former is easy  try all permutations  and the latter is outside the scope of sci.math and more of a computer science problem, although that could change if the problem were reformulated in such a way as to specify a metric for measuring desirability of prospective algorithms.



