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?


  • $\begingroup$ Are you doing AI (artificial intelligence)? $\endgroup$
    – vanCompute
    Oct 15, 2012 at 21:08
  • $\begingroup$ Actually no. Why? $\endgroup$ Oct 16, 2012 at 4:01
  • $\begingroup$ 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? $\endgroup$
    – Paul
    Oct 17, 2012 at 1:12
  • $\begingroup$ 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. $\endgroup$ Oct 17, 2012 at 5:51
  • $\begingroup$ Is there any restriction on the tasks that a given agent can do? $\endgroup$
    – mgriisser
    Nov 21, 2012 at 16:19


Browse other questions tagged or ask your own question.