Algorithms for the one-to-two assignment problem

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.

• 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.) – Kirill Aug 26 '17 at 17:23
• 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). – GoHokies Aug 26 '17 at 18:46
• @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 – physicsGuy Aug 26 '17 at 19:43
• @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. – physicsGuy Aug 26 '17 at 19:48
• Can an agent only be assigned to one task? – spektr Aug 26 '17 at 22:21

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)$.