A sublinear-time randomized approximation algorithm for matrix games

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

zbMATH Keywords

approximation algorithms\(\varepsilon\)-optimal strategiesparallel randomized algorithm\((m, n)\)-matrix game

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) 2-person games (91A05) Parallel numerical computation (65Y05)

Related Items (26)

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

This page was built for publication: A sublinear-time randomized approximation algorithm for matrix games