Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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 constraint $x_{ab} \in \{0,1\}$ and $\sum_b x_{ab} = |B|$ 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.

share|improve this answer
    
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? –  Jan Hadáček Dec 10 '12 at 14:08
    
Round the "soft" assignments, making sure that the constraints are met. –  Hans Engler Dec 10 '12 at 14:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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