An Optimal Randomized Algorithm for Finding the Saddlepoint

Justin Dallant, Frederik Haagensen, Riko Jacob +2

A \emph{saddlepoint} of an $n\times n$ matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum…