The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in [–1, 1]ⁿ, find a signing σ(a) ∊ {±1} of each vector a to minimize the discrepancy ‖ Σ_a σ(a) · a‖_∞. This problem has been extensively studied in the static/offline setting. In this paper we initiate its study in the fully-dynamic setting with recourse: the algorithm sees a stream of T insertions and deletions of vectors, and at each time must maintain a low-discrepancy signing, while also minimizing the amortized recourse (the number of times any vector changes its sign) per update.

For general vectors, we show algorithms which almost match Spencer's offline discrepancy bound, with O(n polylog T) amortized recourse per update. The crucial idea behind our algorithm is to compute a basic feasible solution to the linear relaxation in a distributed and recursive manner, which helps find a low-discrepancy signing. We bound the recourse using the distributed computation of the basic solution, and argue that only a small part of the instance needs to be re-computed at each update.

Since vector balancing has also been greatly studied for sparse vectors, we then give algorithms for low-discrepancy edge orientation, where we dynamically maintain signings for 2-sparse vectors in an n-dimensional space. Alternatively, this can be seen as orienting a dynamic set of edges of an n-vertex graph to minimize the discrepancy, i.e., the absolute difference between in- and out-degrees at any vertex. We present a deterministic algorithm with O(polylog n) discrepancy and O(polylog n) amortized recourse. The core ideas are to dynamically maintain an expander-decomposition with low recourse (using a very simple approach), and then to show that, as the expanders change over time, a natural local-search algorithm converges quickly (i.e., with low recourse) to a low-discrepancy solution. We also give strong lower bounds (with some matching upper bounds) for local-search discrepancy minimization algorithms for vector balancing and edge orientation.