The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in [–1, 1]n, 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.

We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $δ=\frac{8}{5π}\approx 0.509$. This implies that any set of (not necessarily equal) squares of total area $A \leq \frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $\varepsilon>0$ there are sets of squares of total area $\frac{8}{5}+\varepsilon$ that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square $\left(\frac{1}{2}\right)$, circles in a square $\left(\fracπ{(3+2\sqrt{2})}\approx 0.539\right)$ and circles in a circle $\left(\frac{1}{2}\right)$ have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.