Algorithms for finding a \(K\)th best valued assignment (Q1327213)

In a given bipartite graph with weights \(w(e)\) the problem is considered to find the \(K\)th best valued perfect matchings \(M_ k\). This means that there exist perfect matchings \(M_ 1,\dots, M_{k-1}\) s.t. \(w(M_ 1)<\cdots<w(M_ k)< w(M)\) for all perfect matchings \(M\) with \(w(M)\not\in \{w(M_ 1),\dots, w(M_ k)\}\). The algorithms are based on previous work of Murty (1968) and Chegireddy and Hamacher (1987) which allow equality in the ranking inequalities above. Numerical tests on randomly generated problems show the usefulness of the new approach.