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

W.M. Nawijn; B. Dorhout

doi:10.1016/0167-6377(89)90018-7

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

W.M. Nawijn
, B. Dorhout

Research output: Contribution to journal › Article › Academic

6 Citations (Scopus)

185 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 language	Undefined
Pages (from-to)	329-335
Journal	Operations research letters
Volume	8
Issue number	6
DOIs	https://doi.org/10.1016/0167-6377(89)90018-7
Publication status	Published - 1989

Keywords

occupancy problem
Bipartite graph
Linear assignment problem
IR-70401
Matching

Access to Document

10.1016/0167-6377(89)90018-7

Nawijn89on

Cite this

@article{71b77ee844394f76ab79aad39d631bcc,

title = "On the expected number of assignments in reduced matrices for the linear assignment problem",

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.",

keywords = "occupancy problem, Bipartite graph, Linear assignment problem, IR-70401, Matching",

author = "W.M. Nawijn and B. Dorhout",

year = "1989",

doi = "10.1016/0167-6377(89)90018-7",

language = "Undefined",

volume = "8",

pages = "329--335",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

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

AU - Nawijn, W.M.

AU - Dorhout, B.

PY - 1989

Y1 - 1989

N2 - 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.

AB - 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.

KW - occupancy problem

KW - Bipartite graph

KW - Linear assignment problem

KW - IR-70401

KW - Matching

U2 - 10.1016/0167-6377(89)90018-7

DO - 10.1016/0167-6377(89)90018-7

M3 - Article

SN - 0167-6377

VL - 8

SP - 329

EP - 335

JO - Operations research letters

JF - Operations research letters

IS - 6

ER -