Discrepancy Minimization in Input-Sparsity Time
A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal's SDP algorithm for finding a coloring $x \in \{-1, 1\}^n$ that approximately minimizes the discrepancy $\mathrm{disc}(A, x) := | A x |_{\infty}$ of a real-valued $m \times n$ matrix $A$. Larsen's algorithm...
Guardat en:
| Autors principals: | , , , |
|---|---|
| Format: | Article |
| Publicat: |
2022
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2210.12468 http://arxiv.org/abs/2210.12468 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|