Let $A$ and $B$ be two sets with $|A| \ge |B|$, and let $f: C \to \mathbb{R}$ be a nonnegative function with $C \subseteq A×B$. Furthermore, let $D \subseteq C$ be a matching in $C$ such that $D$ provides all the elements of $B$ (through their ordered pairs). How to get

$$D^{*}=\underset{D \subseteq C}{\mathrm{argmin}} \sum_{d \in D}f(d)?$$

Similar question has been raised in A variant of assignment problem (different sizes of sets), but the unequal size problem has not been asnwered.

  • $\begingroup$ As I read it, it was answered. Where in the answer to the linked problem do you see the assumption of equal sizes? $\endgroup$ – quasi Mar 27 '17 at 7:12
  • $\begingroup$ $\sum_{b}x_{a,b}=|B|$ is a real constraint? It should be replaced by $\sum_{b}x_{a,b}=1$ and $\sum_{a}x_{a,b} \le 1$ for all $a \in A$ and $b \in B$, where $x_{a,b} \in \{0,1\}$. $\endgroup$ – Roloka Mar 27 '17 at 7:19
  • $\begingroup$ Right, the posted answer to the linked question is flawed -- your objections are correct. You should post a comment to that answer, raising those objections. But if the posted answer is modified in the way you've suggested, wouldn't it then be correct, and hence, answer your question? $\endgroup$ – quasi Mar 27 '17 at 7:36
  • $\begingroup$ Note that in comparison to the linked question, you've switched the roles of $A,B$, which is somewhat confusing. $\endgroup$ – quasi Mar 27 '17 at 7:39
  • $\begingroup$ Also, can you post a numerical example (or a link to one) for testing? $\endgroup$ – quasi Mar 27 '17 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.