Online vector balancing and geometric discrepancy

We consider an online vector balancing question where T vectors, chosen from an arbitrary distribution over [−1,1] n , arrive one-by-one and must be immediately given a ± sign. The goal is to keep the discrepancy—the ℓ ∞ -norm of any signed prefix-sum—as small as possible. A concrete example of this question is the online interval discrepancy problem where T points are sampled one-by-one uniformly in the unit interval [0,1], and the goal is to immediately color them ± such that every sub-interval remains always nearly balanced. As random coloring incurs Ω( T 1/2 ) discrepancy, while the worst-case offline bounds are Θ(√ n log( T / n )) for vector balancing and 1 for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is Ω( T 1/2 ) for any online algorithm.

Authors

• Nikhil Bansal 0001
• Haotian Jiang
• Sahil Singla 0001
• Makrand Sinha

Keywords

• envy minimization
• online vector balancing
• anti-concentration
• geometric discrepancy