1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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