Vector balancing problem solved with optimal geometric bound
An optimal constant for vector balancing with permutations
Discrete Mathematics
Summary
Balancing vectors with signs and shuffled coordinates can be tricky. The authors looked at a version where each vector can be flipped and its parts rearranged, then found a precise limit for how well this balancing can be done. They showed their bound is the best possible as vectors get bigger. Their proof uses geometric ideas rather than complicated algebra or algorithms.
What this means in practice
- •For system designers: Determine achievable limits of vector balancing when coordinate permutations are allowed to optimize resource allocation algorithms.
- •For communications engineers: Guide signal design methods where vector signs and coordinate order can vary to minimize overall distortion or interference.
A theory result. No direct application yet.
Authors
Jonathan Niles-Weed, Shay Sadovsky, Jacob Shkrob
Abstract
We present a version of the vector balancing problem in which each vector may be given a sign and a permutation of its coordinates. We prove that this vector balancing problem and its corresponding prefix problem admit an explicit bound, and we further show that it is asymptotically optimal in the dimension. Our method of proof is purely geometric.