A sublinear-time randomized approximation algorithm for matrix games
From MaRDI portal
Publication:1919166
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
Cites work
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 724209 (Why is no real title available?)
- scientific article; zbMATH DE number 3069635 (Why is no real title available?)
- A parallel approximation algorithm for positive linear programming
- An iterative method of solving a game
- Convergence rate of the game processes for solving matrix games
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Note on a computation method in the theory of games
- Simple strategies for large zero-sum games with applications to complexity theory
Cited in
(28)- Flows with unit path capacities and related packing and covering problems
- Multicommodity network flows: A survey. II: Solution methods
- On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
- Fast quantum subroutines for the simplex method
- On solving large-scale polynomial convex problems by randomized first-order algorithms
- A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
- Algorithm portfolios for noisy optimization
- Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- Scientific contributions of Leo Khachiyan (a short overview)
- Computer science and decision theory
- Near-linear algorithms for geometric hitting sets and set covers
- Adaptive game playing using multiplicative weights
- The complexity of linear programming in \((\gamma ,\kappa )\)-form
- Finding Sparse Solutions for Packing and Covering Semidefinite Programs
- A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
- Sublinear time algorithms for approximate semidefinite programming
- Random bimatrix games are asymptotically easy to solve (a simple proof)
- Efficient numerical methods to solve sparse linear equations with application to PageRank
- Solving variational inequalities with stochastic mirror-prox algorithm
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- Limits of local search: quality and efficiency
- Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- Fast Algorithms for Rank-1 Bimatrix Games
- Iteration in a subspace for solving matrix games
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)
