English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A \emph{saddlepoint} of an $n \times n$ matrix is an entry that is themaximum of its row and the minimum of its column. Saddlepoints give the\emph{value} of a two-player zero-sum game, corresponding to its pure-strategyNash equilibria; efficiently finding a saddlepoint is thus a natural andfundamental algorithmic task.  For finding a \emph{strict saddlepoint} (an entry that is the strict maximumof its row and the strict minimum of its column) we recently gave an$O({n\log^*{n}})$-time algorithm, improving the $O({n\log{n}})$ bounds from1991 of Bienstock, Chung, Fredman, Sch\"affer, Shor, Suri and of Byrne andVaserstein.  In this paper we present an optimal $O({n})$-time algorithm for finding astrict saddlepoint based on random sampling. Our algorithm, like earlierapproaches, accesses matrix entries only via unit-cost binary comparisons. Forfinding a (non-strict) saddlepoint, we extend an existing lower bound torandomized algorithms, showing that the trivial $O(n^2)$ runtime cannot beimproved even with the use of randomness.

An Optimal Randomized Algorithm for Finding the Saddlepoint