1
$\begingroup$

I can't seem to find a good algorithm for the one-to-exactly-two assignment problem. Good algorithms are known for the classical assignment problem, where N tasks need to be assigned to to M agents in a one-to-one correspondence.

In my case of the one-to-exactly-two assignment problem, I have N tasks and M agents. However, each tasks can only be solved if two agents are assigned to it. Similar to the classical assignment problem, the goal is to minimize the cost, given by a cost matrix $C_{ij}$. Here assigning task $i$ to agent $j$ costs an amount $C_{ij}$.

Any ideas how this can be solved efficiently?

I already considered the review by Pentico, D. 'Assignment Problems: A Golden Anniversary Survey', but could not find my problem there.

$\endgroup$
  • $\begingroup$ Questions like whether a problem is in P could also be on-topic at cs.stackexchange.com, and might get more responses there. (I read this as a complexity theory question, I'm not sure if that's what you intended.) $\endgroup$ – Kirill Aug 26 '17 at 17:23
  • $\begingroup$ have you seen this older scicomp post? it appears to discuss a more general problem than the one you're looking into (many tasks to many agents, not necessarily one-to-one). $\endgroup$ – GoHokies Aug 26 '17 at 18:46
  • $\begingroup$ @Kirill I am looking for an efficient algorithm to solve the problem, I edited my question to clarify that. I am not sure, if in this case CS is the correct stack $\endgroup$ – physicsGuy Aug 26 '17 at 19:43
  • $\begingroup$ @GoHokies Initially I thought this to be the solution. However, the general assignment problem in that post considers at most two agents being assigned to a task. In my case exactly two agents need to be assigned to a task in order to finish it. So the discussion there won't apply here, at least to my understanding. $\endgroup$ – physicsGuy Aug 26 '17 at 19:48
  • $\begingroup$ Can an agent only be assigned to one task? $\endgroup$ – spektr Aug 26 '17 at 22:21
0
$\begingroup$

Not sure if that's a good solution but will post anyways:

Let's assume that we can form a bipartite graph and can solve the one-to-one assignment problem. We will start by assigning the first task in the classical fashion: every node will be assigned to exactly one node in the target. We can then remove the assigned links (edges) from the graph, because these already exist in the previous solution (e.g. we can set the assignment costs to infinity). We could then re-run the assignment algorithm, i.e. Hungarian, and generate the next assignments, which are guaranteed to be different than the first.

Of course this algorithm will probably result in a sub-optimal solution as it looks greedy. Yet, the first solution is always the optimal of the classic assignment problem and it might be a good simple start because this approach allows you to benefit from the existing solvers. Complexity wise it's just $2O(\text{Hungarian})$, which is very acceptable.

In a similar manner, one could use auction algorithms, which might reduce the runtime to $2O(N^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.