Vector Balancing in Polynomial Time
Abstract
The Komlós problem asks for signs ε∈{−1,1}n with |Aε|∞ bounded by an absolute constant whenever the columns of A∈ℝm× n have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic O(√t)-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most t sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.
Related
BibTeX
@misc{guo2026vector,
title = {{Vector Balancing in Polynomial Time}},
author = {Shengtao Guo and Ethan X. Fang and Junwei Lu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23540},
eprint = {2609.23540},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23540},
}
RIS
TY - UNPB
TI - Vector Balancing in Polynomial Time
AU - Shengtao Guo
AU - Ethan X. Fang
AU - Junwei Lu
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23540
UR - https://arxiv.org/abs/2609.23540
AB - The Komlós problem asks for signs ε∈{−1,1}^n with |Aε|_∞ bounded by an absolute constant whenever the columns of A∈ℝ^m× n have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic O(√t)-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most t sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.
ER -