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


Ed Wall
Posts:
36
Registered:
12/3/04


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


>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 NPcomplete, it may be that >a problem is NPcomplete 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.



