The dominance assignment problem

We prove the following remarkable fact for matrices with entries from an ordered set: For any m×nm×n matrix AA and a given integer h≤min{m,n}h≤min{m,n} there exists a matrix C=(cij)C=(cij), obtained from AA by permuting its rows and columns, such that cm−h+i,i≤cjkcm−h+i,i≤cjk for j≤m−h+ij≤m−h+i and i≤ki≤k. Moreover, we give a polynomial algorithm to transform AA into CC. We also prove that when h=m=nh=m=n and all entries of AA are distinct, the diagonal of CC solves the lexicographic bottleneck assignment problem, and that the given algorithm has complexity O(n3n/logn), which is the best performance known for this kind of matrices.