Algorithms for finding a \(K\)th best valued assignment (Q1327213)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for finding a \(K\)th best valued assignment |
scientific article |
Statements
Algorithms for finding a \(K\)th best valued assignment (English)
0 references
18 July 1994
0 references
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.
0 references
assignment
0 references
bipartite graph
0 references
valued perfect matchings
0 references
0 references