@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..",

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

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 Cristopher Moore and Devanur, {Nikhil R.} and Rolim, {Jose D. P.}",

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

address = "Germany",

note = "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",

}