Math Forum Discussions

Ed Wall

Posts: 36
Registered: 12/3/04

Re: Combinatorics Problem
Posted: Feb 25, 1996 5:16 PM

Plain Text

>Hi Ed
>
>> Well, it took less than a second what with putting the stuff on
>> the screen. However, I don't have the right answer it seems. Optimization
>> probs are like that sometimes because of the algorithm. One problem might be
>> I don't switch unless I improve an estimate. It would be interesting to see
>> if this is indeed the problem, but probably I need to sit down and think
>>about
>> the math. Enclosed are my numbers.
>
>I just checked your first few (ie smallest) numbers from each set. According
>to my answer (which may not be unique, of course), about half of your numbers
>are not in the same set as my answer.
>
>So the question is, are you 'close' to the solution or not? If my solution
>is unique, then I would have to say 'no', since you still have to figure out
>which half of each set is wrong, and this is still a mammoth task. (In fact,
>just as mammoth as the original task.)
>
>On the other hand, from a practical viewpoint, you have an error of 48 parts
>in 500 000, which is damn good.
>
>If I understand what it means for a problem to be NP-complete, it may be that
>a problem is NP-complete but still has a rather good algorithm for solving
>it. So maybe 200 numbers is solvable on a home computer but 2000 numbers are
>not.
>
>Anyway, good luck, Ed (and Shane).
>
>Cheers
>
>Rex

Rex

I modified things slightly and got an 'error' of 3 in 500,000. As I
suspected originally the surface I am moving along has 'ruts' to some
extent caused by my formulation of the algorithm. Basically my new approach
was to perturb the solution and then see what happens when the dust settles. As
things stand now I suspect that one could formulate a rather fast algorithm
to find the solution to the numbers you posed (I will leave that to Shane), but
I also suspect that a fast, completely accurate, general one will be hard
to come up with :-)
However, some ideas brought by your original post are nicely illustrated
here. What I have have outlined thanks to Sam is a numerical method and the
first question is how good is it?? Second question is how to best pick
pertubations to gain a degree of confidence (I use this in a loose sense). Third
is it good enough (the calculator question)? All very nice questions IMHO, but
not answered (or even asked) often enough. Thus a nice question for your
students or whoever is how to obtain arbitrarily large errors with this
method (without the pertubations that is).

Ed Wall

P.S. 2,000 numbers would take longer, but I'm not sure things couldn't be
done quite nicely on a home computer (assuming one could handle the sums). As
I mentioned before, there are a few things one could do to speed things up
considerably.