For $A = \{a\_{ij}\} \in R^{n\times n}$, is finding


$$
\max\_{\sigma \in S\_n}\min\_{1 \le i \le n} a\_{i,\ \sigma\_i}
$$


NP-hard?



NP-hardness of finding maximum of minimum element in diagonal of a matrix
This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m\_1 < \dots < m\_\ell$ be the list of edge weights of $G$, let $E\_i$ be the set of edges of weight $m\_i$, and let $G\_i:=G \setminus (E\_1 \cup \dots \cup E\_i)$. Now test if $G\_1$ has a perfect matching (note this can be done in polynomial-time). If no, then the answer is $m\_1$. If yes, then test if $G\_2$ has a perfect matching and recurse. If $k$ is the first index such that $G\_k$ does not have have a perfect matching, then output $m\_k$ as the answer. 


