I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always holds that $|B| \leq |A|$, ie the number of b's will always be less or equal to number of a's.

The task is: For every $b \in B$ find some $a \in A$, minimizing the sum of individual costs, and satisfying the condition that every $b$ is assigned to exactly one $a$, and each $a$ is assigned to one or zero $b$s.

To state it clearly, the assignment satisfying the constraints is a bijective mapping $A^* \rightarrow B$, where $A^* \subseteq A$ and $|A^*|=|B|$.

I think this is a variant of the Assignment problem, but I'm not sure how to modify it to handle the case when the size of sets is not equal (some agents will be idle). Maybe the modification is not trivial, right?

Another idea would be to solve it by a brute-force algorithm assigning the closest unassigned $a$ for each $b$ (one after another) and backtracking when a better assignment for that $a$ is found later, but that's quite ugly.

How to find the optimal assignment efficiently (in polynomial time, if possible)?


1 Answer 1


This is a integer linear programming problem. Let $c_{ab}$ be the cost for the assignment$(a,b)$ and let $x_{ab}$ be 0 or 1 depending on whether this assignment is made or not. The goal is to minimize $$ \sum_{a,b} c_{ab} x_{ab} $$ subject to the constraints $x_{ab} \in \{0,1\}$ and $\sum_a x_{ab} = 1$ for all $b$, $\sum_b x_{ab} \le 1$ for all $a$.

A natural relaxation is to replace the constraints $x_{ab} \in \{0,1\}$ with the inequalities $0 \le x_{ab} \le 1$.

In general, integer programming problems are NP-hard. The relaxed problem however is an ordinary linear programming problems and may be solved efficiently. Specialized software for mixed integer problems may be able to solve also the full problem efficiently.

Problems of this form with $|A|, |B| = O(10^2)$ can be solved in under 1 second in R using the lpSolve package. I don't know how well this scales to larger problem sizes.

  • $\begingroup$ Good answer, I didn't know the problem was NP. I'd upvote (sorry, I can't yet). I'd like to know more about the relaxation in this case. Let's say I solve the relaxed LP problem and I get a vector of the "soft" assignments. Any tips what heuristic should I use to obtain the binary assignment (at least good, if not optimal) from that vector? $\endgroup$ Dec 10, 2012 at 14:08
  • $\begingroup$ Round the "soft" assignments, making sure that the constraints are met. $\endgroup$ Dec 10, 2012 at 14:23
  • $\begingroup$ @Hans Engler: In the comment section of math.stackexchange.com/questions/2204953/…, Roloka raises an objection about your posted answer in this one. You state the constraint $$\text{For all}\;\,a,\;\sum_b x_{ab} = |B|$$ Roloka claims that instead you should have $$\text{For all}\;\,a,\;\sum_{b}x_{a,b}\le1$$ $$\text{For all}\;\,b,\;\sum_{a}x_{a,b}=1$$ It seems to me that Roloka's objection is valid. $\endgroup$
    – quasi
    Mar 27, 2017 at 19:59
  • $\begingroup$ That is indeed correct - thank you. I am editing my post. $\endgroup$ Mar 28, 2017 at 12:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .