Re: proportionality problem
- From: "Gene" <gene.ressler@xxxxxxxxx>
- Date: 25 Feb 2006 22:14:54 -0800
A "greedy" approach ought to work. For each resource i with quality
Q_i, keep track of the number of requests N_i that have been assigned
to it. Let Q be the sum of all Q_i. Also keep track of N the total
number of requests. Then consider the requests one by one in any
order. You'll need to define the "error" in the assignments. One
reasonable choice would be
sum_{i} (Q/Q_i - N_i/N)^2
This error term is zero iff you have a perfect assignment according to
your example. Otherwise it's positive.
So now consider requests in any order. For each possible assignment to
a resource, compute the error that would result and pick the one that
produces the least. If there are many resources, you can use summation
tricks to avoid computing the whole error term for each.
You can fiddle with the definition of error to change the behavior of
the algorithm.
.
- References:
- proportionality problem
- From: Digital Puer
- proportionality problem
- Prev by Date: Re: Data Directed Program Execution
- Next by Date: Re: Assembly: direct video access acts strange
- Previous by thread: Re: proportionality problem
- Next by thread: Re: proportionality problem
- Index(es):
Relevant Pages
|