The cover number of a matrix and its algorithmic applications

DOI10.4230/LIPICS.APPROX-RANDOM.2014.34MaRDI QIDQ2969040zbMATH OpenOpenAlexFDO

Authors Noga Alon, Troy Lee, Adi Shraibman

Publication date 22 March 2017

Full work available at URL https://dr.ntu.edu.sg/bitstream/10356/87666/1/The%20Cover%20Number%20of%20a%20Matrix%20and%20its%20Algorithmic%20Applications.pdf

zbMATH Keywords

approximation algorithmsVC dimensionapproximate Nash equilibriacover number

Mathematics Subject Classification ID

Quadratic programming (90C20) Noncooperative games (91A10) Approximation algorithms (68W25)

Recommendations

• The approximate rank of a matrix and its algorithmic applications
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Polynomial algorithms for approximating Nash equilibria of bimatrix games

Cited in

(6)

• scientific article; zbMATH DE number 7559066 (Why is no real title available?)
• Sparse covers for sums of indicators
• Upper bounds on communication in terms of approximate rank
• scientific article; zbMATH DE number 4044040 (Why is no real title available?)
• scientific article; zbMATH DE number 8033 (Why is no real title available?)
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem

This page was built for publication: The cover number of a matrix and its algorithmic applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969040)