### 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 language | English (US) |
---|---|

Title of host publication | Leibniz International Proceedings in Informatics, LIPIcs |

Editors | Klaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 34-47 |

Number of pages | 14 |

ISBN (Electronic) | 9783939897743 |

DOIs | |

State | Published - Sep 1 2014 |

Externally published | Yes |

Event | 17th 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 2014 → Sep 6 2014 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 28 |

ISSN (Print) | 1868-8969 |

### Other

Other | 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 |
---|---|

Country | Spain |

City | Barcelona |

Period | 9/4/14 → 9/6/14 |

### All Science Journal Classification (ASJC) codes

- Software

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

*Leibniz International Proceedings in Informatics, LIPIcs*(pp. 34-47). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 28). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.34