0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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
    Commented 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. ♦
    Commented May 21, 2021 at 17:21

1 Answer 1

Reset to default
3
$\begingroup$

See Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Do you have a link to that resource? $\endgroup$
    – nir shahar
    Commented 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
    Commented May 21, 2021 at 15:20
  • $\begingroup$ Edit it into the answer :) $\endgroup$
    – nir shahar
    Commented May 21, 2021 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.