Vector Balancing in Polynomial Time

Shengtao Guo, Ethan X. Fang, Junwei Lu

We present a spectral signing algorithm solving the Komlós problem with a constant discrepancy in polynomial time. Given a matrix $A\in {\mathbb{R}}^{m\times n}$ whose columns have Eu…