On the maximum of random assignment process

DOI10.1016/J.SPL.2022.109530MaRDI QIDQ2670804zbMATH OpenOpenAlexWikidataFDO

Authors A. A. Tadevosian, M. A. Lifshits

Publication date 1 June 2022

Published in Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.11390

zbMATH Keywords

assignment problemrandom assignment

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial probability (60C05) Discrete location and assignment (90B80)

Abstract: We describe the behavior of the expectation of the maximum for a random assignment process built upon a square matrix with independent entries. Under mild assumptions on the underlying distribution, the answer is expressed in terms of its quantile function.

Recommendations

• On the Maximum of a Special Random Assignment Process
• Maxima and near-maxima of a Gaussian random assignment field
• On the expected number of assignments in reduced matrices for the linear assignment problem
• Certain expected values in the random assignment problem
• Asymptotics in the random assignment problem

Cites work

• scientific article; zbMATH DE number 1802784 (Why is no real title available?)
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• scientific article; zbMATH DE number 3592801 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Asymptotics in the random assignment problem
• Constructive bounds and exact expectations for the random assignment problem
• Exact solution of the random bipartite matching model
• Maxima and near-maxima of a Gaussian random assignment field
• On the expected value of the minimum assignment
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• The \(\zeta(2)\) limit in the random assignment problem

Cited in

(5)

• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Maxima and near-maxima of a Gaussian random assignment field
• On the Maximum of a Special Random Assignment Process
• Extrema of a multinomial assignment process
• Randomized allocation processes

This page was built for publication: On the maximum of random assignment process

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