The dominance assignment problem

We prove the following remarkable fact for matrices with entries from an ordered set: For any $m\times n$ matrix $A$ and a given integer $h\le min\{m,n\}$ there exists a matrix $C=\left(c_{ij}\right)$ , obtained from $A$ by permuting its rows and columns, such that $c_{m‐h+i,i}\le c_{jk}$ for $j\le m‐h+i$ and $i\le k$ . Moreover, we give a polynomial algorithm to transform $A$ into $C$ . We also prove that when $h=m=n$ and all entries of $A$ are distinct, the diagonal of $C$ solves the lexicographic bottleneck assignment problem, and that the given algorithm has complexity $O\left(n^3\sqrt{n/logn}\right)$ , which is the best performance known for this kind of matrices.