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