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)
    47 Downloads (Pure)

    Abstract

    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
    Volume8
    Issue number6
    DOIs
    Publication statusPublished - 1989

    Keywords

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

    Cite this