# Algorithms for one-to-many assignment problem

I'm looking for a computationally efficient algorithm for solving the following type of assignment problem:

I have two sets of points. Set A has N points and set B has M points. I'd like to establish one-to-many assignments from A to B, where each element in A can have at most two and at least zero matches in B. Obviously, in this bipartite graph the edges have non-zero costs. Also, the matchings are unique - two elements from A cannot be assigned to the same element in B.

I first thought of using the Hungarian algorithm, but it always finds one-to-one matches, which renders it not directly applicable in my case. The sought algorithm should be able to account 1-to-0 and 1-to-2 assignments as well.

Do you know any such algorithm from the literature?

• What is the objective function that you're trying to optimize with those assignments? It would be helpful if you made the question more precise. If members of $A$ and $B$ rank members of $B$ and $A$ and you look for a stable matching, the result would be the hospitals-and-residents problem (aka the college admissions problem), which may be NP-complete. Aug 17 '15 at 15:44
• @Kirill the objective function is a function of the distances of the points and their relative sizes. So, it's nothing too fancy (for now). Yes, I'm looking for a stable matching. I'll check your suggestions - thanks! Aug 18 '15 at 7:16

If $a$ is connected to $b$, add an edge from each of the two copies of $a$ to $b$. Now look for the maximum-weight matching in this bipartite graph. The result will be the solution to your problem.