@inproceedings{f63f3995b2964010a094773526ef84a2,

title = "The cover number of a matrix and its algorithmic applications",

abstract = "Given a matrix A, we study how many ε-cubes are required to cover the convex hull of the columns of A. We show bounds on this cover number in terms of VC dimension and the γ2 norm and give algorithms for enumerating elements of a cover. This leads to algorithms for computing approximate Nash equilibria that unify and extend several previous results in the literature. Moreover, our approximation algorithms can be applied quite generally to a family of quadratic optimization problems that also includes finding the densest κ-by-k combinatorial rectangle of a matrix. In particular, for this problem we give the first quasi-polynomial time additive approximation algorithm that works for any matrix A ∈ [0, 1]m×n..",

keywords = "Approximate Nash equilibria, Approximation algorithms, Cover number, VC dimension",

author = "Noga Alon and Troy Lee and Adi Shraibman",

note = "Publisher Copyright: {\textcopyright} Noga Alon, Troy Lee, and Adi Shraibman.; 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 ; Conference date: 04-09-2014 Through 06-09-2014",

year = "2014",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.APPROX-RANDOM.2014.34",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "34--47",

editor = "Klaus Jansen and Rolim, {Jose D. P.} and Devanur, {Nikhil R.} and Cristopher Moore",

booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",

address = "Germany",

}