2 papers
cs.CC2024
An Optimal Randomized Algorithm for Finding the Saddlepoint
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A \emph{saddlepoint} of an 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…
cs.DS2023
Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A saddlepoint of an matrix is an entry of that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding…