Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, Sebastian Wild · Society for Industrial and Applied Mathematics eBooks · 2024
A saddlepoint of an n × n matrix A is an entry of A that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding a saddlepoint. The worst-case running time of these algorithms is Θ(n2), and Llewellyn, Tovey, and Trick (1988) showed that this cannot be improved, as in the worst case all entries of A may need to be queried.