$\begingroup$
$\endgroup$
2
Consider the standard assignment problem: $n$ people are assigned to n jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) distribution), it is known that the expected sum of costs is $\pi^2/6$.
An alternative solution to the assignment problem is to choose an allocation that instead minimizes the largest cost incurred by any individual, in the spirit of the John Rawls fairness criteria. Is it known what is the random sum of costs in the random version of the problem?
-
$\begingroup$ Can you please provide the weblinks for "expected sum of cost $\pi 2/6$" and "John Rawls fairness criteria". What is the random distribution in your concluding question? $\endgroup$Inuyasha Yagami– Inuyasha Yagami2021年05月21日 10:35:09 +00:00Commented May 21, 2021 at 10:35
-
$\begingroup$ When you copied the text, you didn't preserve the latex. I encourage you to be proofread your text more carefully in the future. $\endgroup$D.W.– D.W. ♦2021年05月21日 17:21:43 +00:00Commented May 21, 2021 at 17:21
1 Answer 1
$\begingroup$
$\endgroup$
3
See Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.
answered May 21, 2021 at 11:45
-
$\begingroup$ Do you have a link to that resource? $\endgroup$nir shahar– nir shahar2021年05月21日 15:13:07 +00:00Commented May 21, 2021 at 15:13
-
$\begingroup$ @nirshahar I found a copy here: math.pugetsound.edu/~mspivey/BAP.pdf. There's also always of course a certain scientific hub. $\endgroup$orlp– orlp2021年05月21日 15:20:59 +00:00Commented May 21, 2021 at 15:20
-
$\begingroup$ Edit it into the answer :) $\endgroup$nir shahar– nir shahar2021年05月21日 15:21:34 +00:00Commented May 21, 2021 at 15:21