The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: optimal sorting
Replies: 3   Last Post: Dec 11, 2012 11:59 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
George Cornelius

Posts: 65
Registered: 12/12/04
Re: optimal sorting
Posted: Dec 10, 2012 12:09 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

nofingers wrote:

> "gsgs" <> wrote in message

>> 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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.