laziness, impatience, and hubris PerlMonks

### Re: Average Price Algorithm

 on Jan 29, 2009 at 17:47 UTC ( #739977=note: print w/replies, xml ) Need Help??

in reply to Average Price Algorithm

I agree with the hunches of my esteemed colleagues -- this problem certainly smells NP-complete. Of course, the details depend on the generalization of the problem, the range of values, and how the objective function is defined (how do you measure "closeness" of a set of numbers to the average?) But since it's probably NP-complete, one would imagine looking for some reasonable heuristics / approximations.

I propose the following mind-numbingly simple algorithm:

1. If a person wants N items, then just allocate a random N items to the person.
Sounds like a joke, but think about it. From each person's point of view, they get a random sample of the available items. That person's "score" is the mean of their sample. But the expected value of a sample mean is the overall mean. So at least in expectation, each person's allocation tends to the overall mean.

Next, the standard approach for "refining" an algorithm that only has good expected performance is:

2. Run many trials of #1 and take the best one
To formally analyze the behavior of the repeated-trials approach, you'd have to do some more statistical analysis that incorporates variances as well (to know how likely each trial is to get close to the objective). I can't make that back-of-the-envelope statistical calculation now, but at least in the sample you gave, the variance among the items seems very small. Thus the variances of the sample means are also small. So I would expect this algorithm to do fairly well. This makes sense, because the difficulty of the problem seems related to how varied the individual items' scores are -- the distribution of the sample mean is greatly influenced by outliers, for example.

Create A New User
Node Status?
node history
Node Type: note [id://739977]
help
Chatterbox?
 [choroba]: but undef %hash and %hash = () both work, too, but the first one keeps the memory allocated, while the latter makes it available for other parts of the program. [choroba]: iirc [perldigious]: karlgoethebier: Well it is a pretty old and complicated (for me) bit of code I wrote (poorly by my current standards), so I'm expecting everything to break when I add the scoping and find out what else is undesireably scope changed. :-) [perldigious]: Ah, thanks choroba, that sort of thing was precisely what I was wondering when I asked. [perldigious]: I didn't want to tie up memory unecessarily basically, I wanted to "delete" it specifically to free it up, and wasn't sure I was even accomplishing that. [stevieb]: perldigious You should start by writing some unit tests. That'll ensure current functionality doesn't break with changes. [choroba]: unit tests++

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2017-07-21 19:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (335 votes). Check out past polls.