Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: optimal sorting
Posted:
Dec 10, 2012 12:09 AM
|
|
nofingers wrote:
>
> "gsgs" <sterten@aol.com> wrote in message
> news:c2a74aef-23b7-4a46-ba73-26926d10baea@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 post-transformation 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.
|
|
|
|
