Premium
A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
Author(s) -
Wästlund Johan
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20066
Subject(s) - conjecture , value (mathematics) , mathematics , combinatorics , expected value , struct , random assignment , discrete mathematics , computer science , statistics , programming language
We prove the main conjecture of the paper “On the expected value of the minimum assignment” by Marshall W. Buck, Clara S. Chan, and David P. Robbins [Random Structures Algorithms 21 (2002), 33–58]. This is an exact formula for the expected value of a certain type of random assignment problem. It generalizes the formula 1 + 1/4 + … 1/ n 2 for the n by n exp(1) random assignment problem. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005