The cover number of a matrix and its algorithmic applications
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 N...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/87666 http://hdl.handle.net/10220/46788 |
| _version_ | 1826120824771313664 |
|---|---|
| author | Lee, Troy Alon, Noga Shraibman, Adi |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Lee, Troy Alon, Noga Shraibman, Adi |
| author_sort | Lee, Troy |
| collection | NTU |
| description | 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}. |
| first_indexed | 2024-10-01T05:22:45Z |
| format | Journal Article |
| id | ntu-10356/87666 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:22:45Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/876662023-02-28T19:23:47Z The cover number of a matrix and its algorithmic applications Lee, Troy Alon, Noga Shraibman, Adi School of Physical and Mathematical Sciences Approximate Nash Equilibria Approximation Algorithms DRNTU::Science::Mathematics 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}. NRF (Natl Research Foundation, S’pore) Published version 2018-12-04T05:29:15Z 2019-12-06T16:46:50Z 2018-12-04T05:29:15Z 2019-12-06T16:46:50Z 2014 Journal Article 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 https://hdl.handle.net/10356/87666 http://hdl.handle.net/10220/46788 10.4230/LIPIcs.APPROX-RANDOM.2014.34 en LIPIcs–Leibniz International Proceedings in Informatics © 2014 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY. 14 p. application/pdf |
| spellingShingle | Approximate Nash Equilibria Approximation Algorithms DRNTU::Science::Mathematics Lee, Troy Alon, Noga Shraibman, Adi The cover number of a matrix and its algorithmic applications |
| title | The cover number of a matrix and its algorithmic applications |
| title_full | The cover number of a matrix and its algorithmic applications |
| title_fullStr | The cover number of a matrix and its algorithmic applications |
| title_full_unstemmed | The cover number of a matrix and its algorithmic applications |
| title_short | The cover number of a matrix and its algorithmic applications |
| title_sort | cover number of a matrix and its algorithmic applications |
| topic | Approximate Nash Equilibria Approximation Algorithms DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/87666 http://hdl.handle.net/10220/46788 |
| work_keys_str_mv | AT leetroy thecovernumberofamatrixanditsalgorithmicapplications AT alonnoga thecovernumberofamatrixanditsalgorithmicapplications AT shraibmanadi thecovernumberofamatrixanditsalgorithmicapplications AT leetroy covernumberofamatrixanditsalgorithmicapplications AT alonnoga covernumberofamatrixanditsalgorithmicapplications AT shraibmanadi covernumberofamatrixanditsalgorithmicapplications |