Algorithms for the one-to-two assignment problem

Question

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.

Answer 1

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