The cover number of a matrix and its algorithmic applications

DOI10.4230/LIPICS.APPROX-RANDOM.2014.34zbMATH Open1359.68297OpenAlexW2122817170MaRDI QIDQ2969040FDOQ2969040

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

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

zbMATH Keywords

approximation algorithmsVC dimensionapproximate Nash equilibriacover number

Mathematics Subject Classification ID

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

Cited In (6)

• Title not available (Why is that?)
• Sparse covers for sums of indicators
• Upper bounds on communication in terms of approximate rank
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)