Order statistics and the linear assignment problem

DOI10.1007/BF02310105MaRDI QIDQ1098186zbMATH OpenFDO

Authors J. B. G. Frenk, M. van Houweninge, Alexander H. G. Rinnooy Kan

Publication date 1987

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02310105

zbMATH Keywords

asymptotic behavior in expectationasymptotic estimatesexpected optimal value of the linear assignment problemsmallest order statistic

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Order statistics; empirical distribution functions (62G30) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Review text

Under mild conditions on the distribution function F, we analyze the asymptotic behavior in expectation of the smallest order statistic, both for the case that F is defined on \((-\infty,+\infty)\) and for the case that F is defined on (0,\(\infty)\). These results yield asymptotic estimates of the expected optimal value of the linear assignment problem under the assumption that the cost coefficients are independent random variables with distribution function F.

Recommendations

• The random linear bottleneck assignment problem
• On the expected number of assignments in reduced matrices for the linear assignment problem
• Certain expected values in the random assignment problem
• On the expected optimal value of random assignment problems: Experimental results and open questions
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3885046 (Why is no real title available?)
• Matchings in random regular bipartite digraphs
• On the Expected Value of a Random Assignment Problem

Cited in

(6)

• Statistical applications of linear assignment
• On the expected optimal value of random assignment problems: Experimental results and open questions
• On the expected number of assignments in reduced matrices for the linear assignment problem
• The random linear bottleneck assignment problem
• On the Maximum of a Special Random Assignment Process
• Random assignment problems

This page was built for publication: Order statistics and the linear assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098186)