The cover number of a matrix and its algorithmic applications

Noga Alon, Troy Lee, Adi Shraibman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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..

Original languageEnglish (US)
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
EditorsKlaus Jansen, Jose D. P. Rolim, Nikhil R. Devanur, Cristopher Moore
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages34-47
Number of pages14
ISBN (Electronic)9783939897743
DOIs
StatePublished - Sep 1 2014
Externally publishedYes
Event17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain
Duration: Sep 4 2014Sep 6 2014

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume28
ISSN (Print)1868-8969

Other

Other17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
Country/TerritorySpain
CityBarcelona
Period9/4/149/6/14

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximate Nash equilibria
  • Approximation algorithms
  • Cover number
  • VC dimension

Fingerprint

Dive into the research topics of 'The cover number of a matrix and its algorithmic applications'. Together they form a unique fingerprint.

Cite this