Balancing vectors in any norm

Autor: Nicole Tomczak-Jaegermann, Kunal Talwar, Daniel Dadush, Aleksandar Nikolov
Přispěvatelé: Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: FOCS
Popis: In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside β K. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl.~Math '81), Spencer's "six standard deviations suffice" theorem (Trans.~Amer.~Math.~Soc '85) and Banaszczyk's vector balancing theorem (Random Structures & Algorithms '98) correspond to bounds on vector balancing constants. The above theorems have inspired much research in recent years within theoretical computer science. In this work, we show that all vector balancing constants admit "good" approximate characterizations, with approximation factors depending only polylogarithmically on the dimension n. First, we show that a volumetric lower bound due to Banaszczyk is tight within a O(log n) factor. Our proof is algorithmic, and we show that Rothvoss's (FOCS '14) partial coloring algorithm can be analyzed to obtain these guarantees. Second, we present a novel convex program which encodes the "best possible way" to apply Banaszczyk's vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an O(log^2.5 n) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm.
Databáze: OpenAIRE
Externí odkaz: