Online Discrepancy with Recourse for Vectors and Graphs

e vector-balancing problem is a fundamental problem in discrepancy theory: given 𝑇 vectors in [-1, 1] 𝑛 , find a signing 𝜎 (𝑎) ∈ ±1 of each vector 𝑎 to minimize the discrepancy 𝑎 𝜎 (𝑎) • 𝑎 ∞ . is problem has been extensively studied in the static/o ine se ing. In this paper we initiate its study in the fully-dynamic se ing with recourse: the algorithm sees a stream of 𝑇 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 𝑂 ( √ 𝑛) o ine discrepancy bound, with 𝑂 (𝑛 polylog𝑇 ) amortized recourse per update.

e 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 𝑛dimensional space. Alternatively, this can be seen as orienting a dynamic set of edges of an 𝑛-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 𝑂 (polylog 𝑛) discrepancy and 𝑂 (polylog 𝑛) amortized recourse.

e 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.