I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf

It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best. However, it only looks at perfect matchings. I'm am especially interested in bipartite matchings.

In particular, for the bipartite graphs, the Theorem 1 p. 161 uses the fact that the matchings are considered perfect.

How can I solve the k-best assignment problem for general bipartite graphs?


After some thinking, I found an answer. If one has a better one I'll accept it.

From a cost matrix of shape $n\times m$ with $n<m$, it is easy to add nodes that will not change anything by giving all their incident edges the same weight $w$, that is adding $(m-n)*m$ edges.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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