Min max solution to the random assignment problem
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.