On the recognition of permuted bottleneck Monge matrices (Q1902890)

A rectangular matrix is called a bottleneck Monge matrix if for every \(2\times 2\) submatrix the larger entry on the main diagonal does not exceed the larger entry on the skew diagonal. The main result is that the complexity of recognizing if an \(n\times m\) \((0, 1)\)-matrix is permutable to a bottleneck Monge matrix is of order \(O(nm(n+ m))\).