Approximated assignment problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
ironman
New poster
Posts: 1
Joined: Tue Jul 20, 2010 5:31 am

Approximated assignment problem

Post by ironman » Tue Jul 20, 2010 5:39 am

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?

wrummler
New poster
Posts: 2
Joined: Mon Nov 29, 2010 10:35 pm

Re: Approximated assignment problem

Post by wrummler » Thu May 19, 2011 4:27 am

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)

surbhi
New poster
Posts: 2
Joined: Mon Nov 05, 2012 11:50 pm

Re: Approximated assignment problem

Post by surbhi » Fri Nov 09, 2012 11:24 pm

can any one give me tight example for bin packing ...?

jony33
New poster
Posts: 2
Joined: Sat Oct 11, 2014 11:56 am

Re: Approximated assignment problem

Post by jony33 » Sat Oct 11, 2014 12:02 pm

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.

Post Reply

Return to “Algorithms”