Min max solution to the random assignment problem

Question

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 costs incurred by any individual, in the spirit of the John Rawls fairness criteria (see here). Is it known any algorithm that finds such maximin allocation, and is it known what is the random sum of costs in the random version of the problem?

Many thanks,

Answer 1

Yes, there is an efficient algorithm to find an assignment that minimizes the largest cost. Suppose we want to check whether there is an assignment with largest cost $t$. To do that, delete all edges with cost larger than $t$, ignore the costs, and check whether the graph has a bipartite matching using the Hopcroft-Karp algorithm; if it does, there is a valid assignment. Now use binary search over $t$ until you find the minimum $t$ such that a valid assignment exists. Thus, the problem can be solved $O(|E| \sqrt{|V|} \lg |E|)$ time.