# Algorithm for K-best NON perfect bipartite matchings

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, 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.