A sublinear-time randomized approximation algorithm for matrix games
From MaRDI portal
Publication:1919166
DOI10.1016/0167-6377(95)00032-0zbMath0857.90144OpenAlexW2053924317MaRDI QIDQ1919166
Michael D. Grigoriadis, Leonid G. Khachiyan
Publication date: 11 March 1997
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(95)00032-0
approximation algorithms\(\varepsilon\)-optimal strategiesparallel randomized algorithm\((m, n)\)-matrix game
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) 2-person games (91A05) Parallel numerical computation (65Y05)
Related Items
Algorithm portfolios for noisy optimization, Efficient numerical methods to solve sparse linear equations with application to PageRank, Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design, Sublinear time algorithms for approximate semidefinite programming, The complexity of linear programming in \((\gamma ,\kappa )\)-form, Finding Sparse Solutions for Packing and Covering Semidefinite Programs, On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms, A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs, Randomized first order algorithms with applications to \(\ell _{1}\)-minimization, A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs, Unnamed Item, A nearly linear-time PTAS for explicit fractional packing and covering linear programs, Scientific contributions of Leo Khachiyan (a short overview), Towards more practical linear programming-based techniques for algorithmic mechanism design, Limits of local search: quality and efficiency, Computer science and decision theory, Near-linear algorithms for geometric hitting sets and set covers, Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs, Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control, On randomized fictitious play for approximating saddle points over convex sets, Fast quantum subroutines for the simplex method, Adaptive game playing using multiplicative weights, Flows with unit path capacities and related packing and covering problems, Solving variational inequalities with Stochastic Mirror-Prox algorithm, On Solving Large-Scale Polynomial Convex Problems by Randomized First-Order Algorithms, On the efficiency of a randomized mirror descent algorithm in online optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An iterative method of solving a game
- Simple strategies for large zero-sum games with applications to complexity theory
- Note on a computation method in the theory of games
- Convergence rate of the game processes for solving matrix games
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- A parallel approximation algorithm for positive linear programming
