All Publications

Finding the saddlepoint faster than sorting

Jan 2024 (Written: Jul 2023)

Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild:

Symposium on Simplicity in Algorithms (SOSA) 2024

| read herePDFDOI arXiv |

The saddlepoint of a matrix is an entry that is simultaneously the minimum in its column and the maximum in its row. Note that not every matrix has a saddlepoint.

The complexity of finding a saddlepoint if it exists strongly depends on details of the definition: If min and max are non-strict, then $\Theta(n^2)$ time is necessary and sufficient for an $n\times n$ matrix; if min and max must be strict, however, almost-linear time is possible (and most entries in the matrix need not be inspected).

a matrix with a strict sadlepoint
A $9 \times 9$ matrix $A$ with a (strict) saddlepoint at $a_{5,5} = 0$. In the 3D plot of the matrix entries, the saddlepoint highlighted in green.

The clean and simple algorithm from Bienstock, Chung, Fredman, Schäffer, Shor, and Suri (1991) effectively requires sorting $n$ elements and achieves an overall time of $O(n \log n)$. This made it look like sorting could be a necessary bottleneck, especially when trying to certify that a matrix has no saddlepoint. Alas, we show that this is not true; an entirely different approach via the relaxed notion of a pseudo saddlepoint allows in $O(n \log^* n)$ time to reduce the search space for possible saddlepoints to a single value, which can then be checked in linear time.