Please use this identifier to cite or link to this item:
Title: The cover number of a matrix and its algorithmic applications
Authors: Lee, Troy
Alon, Noga
Shraibman, Adi
Keywords: Approximate Nash Equilibria
Approximation Algorithms
Issue Date: 2014
Source: Alon, N., Lee, T., & Shraibman, A. (2014). The cover number of a matrix and its algorithmic applications. LIPIcs–Leibniz International Proceedings in Informatics, 34-47. doi:10.4230/LIPIcs.APPROX-RANDOM.2014.34
Series/Report no.: LIPIcs–Leibniz International Proceedings in Informatics
Abstract: Given a matrix A, we study how many epsilon-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 gamma_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 k-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 in [0,1]^{m x n}.
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.34
Rights: © 2014 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
The Cover Number of a Matrix and its Algorithmic Applications.pdf464.22 kBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.