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

<p>From a cost matrix of shape <span class="math-container">$n\times m$</span> with <span class="math-container">$n&lt;m$</span>, it is easy to add nodes that will not change anything by giving all their incident edges the same weight <span class="math-container">$w$</span>, that is adding <span class="math-container">$(m-n)*m$</span> edges.</p>

CC BY-SA 4.0
2019-01-07T08:49:11.787Z
2019-01-07T12:48:54.013Z
2019-01-07T12:48:54.013Z
Labo
<p>I was reading this great article: <a href="https://core.ac.uk/download/pdf/82129717.pdf" rel="nofollow noreferrer">https://core.ac.uk/download/pdf/82129717.pdf</a></p>

<p>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.</p>

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

<p>How can I solve the k-best assignment problem for general bipartite graphs?</p>

<graph-algorithms><matching><bipartite-graphs>
Algorithm for K-best NON perfect bipartite matchings
Labo
# Algorithm for K-best NON perfect bipartite matchings

(Asked by: username_0 on 2019-01-06)

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?

**Tags:** graph-algorithms, matching, bipartite-graphs

---

## 1 answers

### Answer by username_0 on 2019-01-07. Score: 1

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.


---

