تقرير
An Optimal Randomized Algorithm for Finding the Saddlepoint
| العنوان: | An Optimal Randomized Algorithm for Finding the Saddlepoint |
|---|---|
| المؤلفون: | Dallant, Justin, Haagensen, Frederik, Jacob, Riko, Kozma, László, Wild, Sebastian |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, F.2.0 |
| الوصف: | 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 game, corresponding to its pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental algorithmic task. For finding a \emph{strict saddlepoint} (an entry that is the strict maximum of 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 from 1991 of Bienstock, Chung, Fredman, Sch\"affer, 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^2)$ runtime cannot be improved even with the use of randomness. Comment: 12 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2401.06512 |
| رقم الأكسشن: | edsarx.2401.06512 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |