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
    0 references
    0 references
    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

    Identifiers