2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kirill
    Aug 17, 2015 at 15:44
  • $\begingroup$ @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! $\endgroup$
    – xeroqu
    Aug 18, 2015 at 7:16

2 Answers 2

Reset to default
1
$\begingroup$

I would initiate my problem with a Hungarian algorithm. This gives you the minimum cost assignment. Then, I would follow a greedy procedure: Pick a point in A and assign it to the point in B, having the closest distance to the first assignment (obtained via Hungarian). If this point already contains 2 matches, skip to the next one in B (If your assignments are unique, this will never happen). Then, take second point in A and iterate. You could do this efficiently by maintaining a dynamic LUT over the set B.

This is of course greedy and by no means optimal. However, my experience is that such algorithms give reasonable results in practice.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If I understand your answer correctly, you're suggesting running the Hungarian once to get the first min cost matching and then for each element in A, remove its min-cost match in B and re-running the Hungarian algorithm to find the second-best min-cost match? I briefly thought about this, but the computational cost of this would be just too high [O(n^4)] $\endgroup$
    – xeroqu
    Aug 17, 2015 at 8:50
1
$\begingroup$

This problem can be solved by the Hungarian algorithm (or any other algorithm for the assignment problem). Simply make two copies of each element of A.

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.

This finds the exact global optimum solution to your problem, efficiently. You don't have to settle for an approximation or local optimum; this finds the best possible solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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