A sublinear-time randomized approximation algorithm for matrix games
DOI10.1016/0167-6377(95)00032-0zbMATH Open0857.90144OpenAlexW2053924317MaRDI QIDQ1919166FDOQ1919166
Authors: M. 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
Recommendations
- A subexponential randomized algorithm for the simple stochastic game problem
- A randomized subexponential algorithm for parity games
- Fast algorithms for finding randomized strategies in game trees
- A Deterministic Subexponential Algorithm for Solving Parity Games
- A subexponential lower bound for the random facet algorithm for parity games
approximation algorithmsparallel randomized algorithm\(\varepsilon\)-optimal strategies\((m, n)\)-matrix game
Parallel numerical computation (65Y05) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Simple strategies for large zero-sum games with applications to complexity theory
- An iterative method of solving a game
- A parallel approximation algorithm for positive linear programming
- Note on a computation method in the theory of games
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Title not available (Why is that?)
- Convergence rate of the game processes for solving matrix games
Cited In (29)
- Solving variational inequalities with stochastic mirror-prox algorithm
- A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
- Algorithm portfolios for noisy optimization
- Fast Algorithms for Rank-1 Bimatrix Games
- Sublinear time algorithms for approximate semidefinite programming
- Finding Sparse Solutions for Packing and Covering Semidefinite Programs
- On randomized fictitious play for approximating saddle points over convex sets
- Adaptive game playing using multiplicative weights
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control
- Random bimatrix games are asymptotically easy to solve (a simple proof)
- The complexity of linear programming in \((\gamma ,\kappa )\)-form
- Efficient numerical methods to solve sparse linear equations with application to PageRank
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Iteration in a subspace for solving matrix games
- Flows with unit path capacities and related packing and covering problems
- Fast quantum subroutines for the simplex method
- Near-linear algorithms for geometric hitting sets and set covers
- A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- On solving large-scale polynomial convex problems by randomized first-order algorithms
- Computer science and decision theory
- Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- Scientific contributions of Leo Khachiyan (a short overview)
- On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
- Limits of local search: quality and efficiency
- Multicommodity network flows: A survey. II: Solution methods
This page was built for publication: A sublinear-time randomized approximation algorithm for matrix games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1919166)
