Conference rusure::math

    Re .0:
    
    There can be infinitely many limits, such as one z for each possible x
    and y in (x y z).  It would help to know more about the function -- do
    we know anything about what properties it has?
    
    Also note that (2 2 2) might be a low limit if you change the third
    number but not if you change the first or second.  Should your
    algorithm present that information? 
    
    
    				-- edp

	I'm curious what application this is for.

	Dan

    I would be interested in a second explanation of the problem.

Thanks for the replies so far.  Sorry if this is sounding a bit sketchy, i'll
try to fill in more details [a bit at a time].

re .1:

>    There can be infinitely many limits, such as one z for each possible x
>    and y in (x y z).  It would help to know more about the function -- do
>    we know anything about what properties it has?

For now, we can assume that the function will change value over a "reasonable"
period... (i think the algorithm may have to account for a function which
doesn't meet this assumption, but that's an exception that we probably don't
need to discuss here.)
    
>    Also note that (2 2 2) might be a low limit if you change the third
>    number but not if you change the first or second.  Should your
>    algorithm present that information? 

No;  that is what was meant by "maximized cases"... the low/med-limits should
only consist of lists with elements that are at their "highest" limit (doubt
that makes any more sense!)...

re .2:
>	I'm curious what application this is for.

System Level Design Analysis is the name of the group/project/application.
actually this is an "experiment" within that project: in brief (since i'm
trying to keep this topic focused on the algorythmic problem) we're going
to take 100's of computer system configurations, all of the "link paths"
within the configurations, and analyze them for bus utilization (the
"function" is based on emperical results)...  anyway, the real job is
presenting and using it, but we've got to get past a few hurdles (like this
one)!

re .3: >    I would be interested in a second explanation of the problem.

i hope you're at least 1/2 joking!   (i was thinking of extracting .0 and
using that as the documentation to the algorithm i have!... ;-)

thanks again,
jonathan

> re .3: >    I would be interested in a second explanation of the problem.
> 
> i hope you're at least 1/2 joking!   (i was thinking of extracting .0 and
> using that as the documentation to the algorithm i have!... ;-)
    
    I'm dead serious, but you can blame me for being thick-headed if you
    like.  (There are times when I feel that way about others in this file).
    
    Exactly what "rule" is followed to determine if (a b c) or for
    that matter (a b c d e f g) is LO, MED or HI?  Or, to ask it yet
    another way, if the outputs are one of {LO, MED, HI}, what are
    the input(s) and how are they processed to produce the outputs?
    
      John

     The function that maps (244,11,1099) into one of {LO, MED,
     HI} is given to you.  You don't need to know any more about
     it, other than x <= x', y <= y', z <= z' implies that
     f(x,y,z) <= f(x',y',z'), where results are ordered LO <= MED
     <= HI.
     
     The problem is to specify an algorithm that can take any
     such function and find the maximal whatever_he_called_them_-
     in_.0's.
     
     Dan

>     The function that maps (244,11,1099) into one of {LO, MED,
>     HI} is given to you.  
    
    More to the point, it ISN'T given to you.  Nor does it depend on when
    it is fed its inputs.  Two points that weren't clear to me.
    
      John

	My understanding of the problem is as follows.

	Let P* be the set of lists of strictly positive integers.   Let
Q be a fixed, finite totally ordered set (in this case {LO,MED,HI}).
Let M be the set of monotonic functions from P* to Q, ie. functions, f, from
P* to Q which satisfy for all positive integers, I,p_1,...p_I,p'_1,...p'_I:

	(for all i = 1...I, p_i =< p'_i)  implies
	f(p_1, ..., p_I) =< f(p'_1, ..., p'I)

	Given f in M, we want an algorithm which yields us the subset L
of P* of locally maximal lists.   A list, l= (p_1, ..., p_I) is locally maximal
if for all lists l' = (p'_1, ..., p'_I):

	(for all i = 1...I, p_i =< p'_i)  implies
	f(p_1, ..., p_I) < f(p'_1, ..., p'I)

	(That's now a strict inequality).

*******************************************************************************

	Parenthetically, can I make a suggestion to a moderator.   Quite often,
problems associated with real projects appear here.   However, frequently, we
have difficulty in understanding what the underlying problem is, because the
problem is presented in a confused way, or information is omitted, or technical
terms which are not generally known appear.

	Also, often the problem as it is described is only a subpart of a wider
context, and in fact is not the correct problem to be addressing.  One needs
to know the wider context in order to advise what the best approach would be.
Also, regulars of this conference are just plain *curious* to know where a
certain abstract problem has cropped up.

	So, can I suggest a modification to 1.0, or alternatively
a 'set conference /notice="read note xxx"', which advises people who enter
this conference with real work related problems to:

	(1) State their problem as clearly and as completely as possible in 
language that a computer-illiterate person could understand.

	(2) Afterwards, include something about the context and the 
significance of the problem to the project.

*******************************************************************************

I'll put my ideas about solving the problem in hand in the next reply.

Regards,
Andrew.

	With the definition of the problem as in -.1, there is no
interaction between f operating on lists of different length.   So let's
treat them independently.   Let N be the length of the lists we are
currently investigating.   Use the notation of -.1, and say P^N is the
set of lists of length N, over the positive integers.

	When searching for L, we'll need some kind of assumption about
how f behaves when the arguments take large values, otherwise you could
keep on searching for ever.   Eg.  suppose f(x) = LO forall x is a legitimate
function.   When does the algorithm stop computing f?   Perhaps the
orginator of the problem can provide an indication of what an appropriate
assumption might be.

N=0.   The empty list is locally maximal for all f in M.   It is possible
for it to be HI and still be locally maximal, something which is impossible
for all other N!

N=1.	L contains at most |Q|-1 elements.   If it contains exactly |Q|-1,
then f is uniquely defined by L.   To find L, calculate f(x) for x "as large
as is reasonable", and then try f(x/2) if necessary etc.

N=2.   Regard P^2 as a quarter plane.   L can be arbitrarily large but is
finite (if (x,y) is in L, then there at most x-1 + y-1 other lists in L
with the same value of f).   To find L, again divide and conquer seems to be
be most efficient.

It's clear that whatever finite value N takes, L is finite.   Suppose l =
(p_1,..p_N) is in L.   Then the range in which other lists in L with the
same f-value can be found is:

UNION ( i = 1..N) (c < p_i) X(i,c)

where X(i,c) = {(q_1,...q_N) such that q_i = c}

	But there are only a finite number of X(i,c), and by induction on N,
we can say that each X(i,c) contains only a finite number of elements of L.
Since Q itself is finite, L must be finite.

	Really, with no more knowledge of f, there's not much more one
can say, I think.

Andrew.

    re: .6, .7
    
    right-on.... there will be more than one function, [depending on the
    data, user, etc.], but each function must meet the aforementioned
    criteria [which you've "forced" out of me ;-)].  Sorry again for not
    being totally clear...
    
    re: .8
    
    looks like an accurate and complete description of the problem (but
    then, i sure wouldn't be able to catch any glitches in those formulas,
    if there were any!)..  wish i could've stated it like that in .0!
    
    (as far as the parenthetical suggestions - i don't think my .0 would
    have been much different... at the time, i'm sure i thought i was being
    as understandable as possible!)
    
    re: .9
    
>	When searching for L, we'll need some kind of assumption about
>how f behaves when the arguments take large values, otherwise you could
>keep on searching for ever.   Eg.  suppose f(x) = LO forall x is a legitimate
>function.   When does the algorithm stop computing f?   Perhaps the
    
    as stated in .4 (i have the benefit of a print-out of all the replies
    so far!), we're assuming the function will change value over a
    "reasonable" period...  that assumption therefore becomes a necessary
    criteria for any functions we use, and [the function implementors] will
    have to ensure it is true.  the algorithm should then not have to take
    that example into consideration...
    
    one more "simplifying assumption" we can make (these things just keep
    coming): we will only have to deal with N>=2 (using .8,.9's
    definitions).
    
    about the "divide and conquer" approach... i think that was the heart
    of my question...  in fact, i have since gotten a "divide and conquer"
    approach worked out & [i believe] operating.  the next time i get a
    chance, i will try to describe this approach with respect to P*, Q,
    etc.
    
    thanks a bunch (especially for the re-"word"ing of the problem),
    Jonathan