Algorithm for K-best NON perfect bipartite matchings 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&lt;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.