# A variant of the assignment problem (?) [duplicate]

Possible Duplicate:
A variant of the Assignment Problem

(Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.)

In my variant of the problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task needs to be assigned to exactly $m$ or $m+1$ agents.

It is guaranteed that this is possible: the segment $[ |A|n, |A|(n+1) ]$ intersects the segment $[ |B|m, |B|(m+1) ]$.

Each agent-task combination yields a profit, and I want to maximize the profit.

Is this a special case of one of the known problems? How can this be solved? If not practical for $n=100000$, what are good approximations and what is their complexity?

Cheers!

• Are you doing AI (artificial intelligence)?
– vanCompute
Oct 15, 2012 at 21:08
• Actually no. Why? Oct 16, 2012 at 4:01
• Hi NitzanShaked. Welcome to Scicomp! Let me see if I understand this correctly: Each agent is assigned roughly the same number of tasks and each task need to be assigned to a nearly equal number of agents. This is the case you're investigating, right?
– Paul
Oct 17, 2012 at 1:12
• You understand correctly. A clarification, though: the "roughly same number of tasks" (call that "n") and "nearly equal number of agents" (call that "m") requirement yields a set of solutions. For example: if (n,m) is a solution then so are (if the population is large enough) (2n,2m), etc. So in a specific instance of my problem I have given "n" and "m", but yes you got it. Oct 17, 2012 at 5:51
• Is there any restriction on the tasks that a given agent can do? Nov 21, 2012 at 16:19