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

On the other hand, I've never looked for an approximation algorithm for it. Maybe there's a sub-cubic time one?

... 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.

**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)**### 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.