I'm trying to find a suitable algorithm for the following problem.
We have n computers with a1, a2, a3,....,an processing powers. We have m (m >> n) number of tasks which require b1, b2,....bm amount of work to do.
Distribute all of those m tasks among the n computers so that the ratios of work computers have to do are approximately a1:a2:a3:....:an. One task is assigned only to one machine and no tasks should be left out without assignment.
In most of the cases, the ratio a1:a2:....:an may not be possible to achieve, so only an approximation is needed.
Brute forcing can't be applied here since m can be large.
Can anyone please mention an algorithm to come up with an acceptable solution to this problem?
Approximated assignment problem
Moderator: Board moderators
Re: Approximated assignment problem
The assignment problem can be exactly solved in cubic time by the Hungarian method (aka the Kuhn-Munkres algorithm), no need for approximation or brute force. There's implementations floating around all over the internet. (Even I wrote one --- http://www.cs.princeton.edu/~ken/hungar ... hod.tar.gz --- as an errata supplement for a book on combinatorial optimization.)
On the other hand, I've never looked for an approximation algorithm for it. Maybe there's a sub-cubic time one?
(edit)
... I think I saw "assignment problem" in your thread title and saw the basic processor/task structure you have, and I assumed you were talking about an approximation algorithm for the assignment problem. Whereas, it seems your problem is only superficially similar to the assignment problem.
Perhaps an idea: Let A be the sum of your "processor powers", and let B be the sum of your task work-amounts. For each processor i, let the "ratios of work" be r_i = ( a_i / A ) * B. This does not reduce your problem to the assignment problem, at least not outright. Your problem makes me think of bin-packing, but I'm only familiar with bin-packing where the bin size is fixed and the number of bins is to be minimized, versus here, where the "bin size" r_i is variable and the number of "bins" n is fixed.
(/edit)
On the other hand, I've never looked for an approximation algorithm for it. Maybe there's a sub-cubic time one?
(edit)
... I think I saw "assignment problem" in your thread title and saw the basic processor/task structure you have, and I assumed you were talking about an approximation algorithm for the assignment problem. Whereas, it seems your problem is only superficially similar to the assignment problem.
Perhaps an idea: Let A be the sum of your "processor powers", and let B be the sum of your task work-amounts. For each processor i, let the "ratios of work" be r_i = ( a_i / A ) * B. This does not reduce your problem to the assignment problem, at least not outright. Your problem makes me think of bin-packing, but I'm only familiar with bin-packing where the bin size is fixed and the number of bins is to be minimized, versus here, where the "bin size" r_i is variable and the number of "bins" n is fixed.
(/edit)
Re: Approximated assignment problem
can any one give me tight example for bin packing ...?
Re: Approximated assignment problem
Distribute all of those m tasks among the n computers so that the ratios of work computers have to do are approximately a1:a2:a3:....:an. One task is assigned only to one machine and no tasks should be left out without assignment.