DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.44

An Optimal Randomized Algorithm for Finding the Saddlepoint

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

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

A saddlepoint of an n × n matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the value of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental algorithmic task. For finding a strict saddlepoint (an entry that is the strict maximum of its row and the strict minimum of its column) an O(n log* n)-time algorithm was recently obtained by Dallant, Haagensen, Jacob, Kozma, and Wild, improving the O(n log n) bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein. In this paper we present an optimal O(n)-time algorithm for finding a strict saddlepoint based on random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unit-cost binary comparisons. For finding a (non-strict) saddlepoint, we extend an existing lower bound to randomized algorithms, showing that the trivial O(n²) runtime cannot be improved even with the use of randomness.

Cite as

Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild. An Optimal Randomized Algorithm for Finding the Saddlepoint. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 44:1-44:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dallant_et_al:LIPIcs.ESA.2024.44,
  author =	{Dallant, Justin and Haagensen, Frederik and Jacob, Riko and Kozma, L\'{a}szl\'{o} and Wild, Sebastian},
  title =	{{An Optimal Randomized Algorithm for Finding the Saddlepoint}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{44:1--44:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.44},
  URN =		{urn:nbn:de:0030-drops-211154},
  doi =		{10.4230/LIPIcs.ESA.2024.44},
  annote =	{Keywords: saddlepoint, matrix, comparison, search, randomized algorithms}
}

Search Results

Documents authored by Haagensen, Frederik

An Optimal Randomized Algorithm for Finding the Saddlepoint

Abstract

Cite as

Thanks for your feedback!

Could not send message