2
$\begingroup$

In the following Wikipedia article about the Assignment Problem in the Example section, it says:

Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.

I have a problem where an agent can do several tasks and a task can be assigned to multiple agents. The only two contraints are:

  1. to have everyone working and all tasks are assigned

  2. no length 3 path, meaning if an agent is working on several tasks, non of these tasks will be assigned to different agents.

Maybe a variantion of Hungarian Algorithm can apply here, but I can not find how would that be.

I'd really appreciate if anyone can help me, or guide me to where I can find the solution.

Thanks.

1 Answers 1

1

Assignment problem is simply a special case of a transportation problem and in turn a very very special of a simple LPP. Therefore, if there is any deviation from the usual structure, we should be good with reverting to the back-end.