On the expected number of assignments in reduced matrices for the linear assignment problem

W.M. Nawijn, B. Dorhout

    Research output: Contribution to journalArticleAcademic

    6 Citations (Scopus)
    144 Downloads (Pure)


    A linear n × n assignment problem is considered for which the elements of the cost matrix are sampled from a continuous probability distribution. Based on the zero entries of the reduced matrix the expectation of the maximum number of initial assignments is determined for general n, as well as an asymptotic value for large n.
    Original languageUndefined
    Pages (from-to)329-335
    JournalOperations research letters
    Issue number6
    Publication statusPublished - 1989


    • occupancy problem
    • Bipartite graph
    • Linear assignment problem
    • IR-70401
    • Matching

    Cite this