Algorithm for the minimax assignment problem with a sparse rectangular matrix (Q580163)

The considered problem may be stated as follows. Given is an \(m\times n\) rectangular matrix A with elements a(i,j). Some of the elements are inadmissible and may remain undefined. A diagonal of this matrix is defined as any collection of m matrix elements such that not two are in the same column or in the same row. A diagonal of the matrix A is admissible if it contains no inadmissible elements. The goal is to find an admissible diagonal with the smallest maximal element. In the paper, a new algorithm for the minimax assignment problem is proposed. It behaves particularly well for sparse and rectangular matrices (i.e. those where there are many inadmissible elements and \(m<n)\).