Greedy Vector Balancing

Abstract

In online vector balancing, vectors $t_1,\dots ,t_n$ arrive one by one from a given set $T$ and the goal is to assign signs $s_1,\dots ,s_n\in \{\pm 1\}$ in an online manner so as to minimize the largest norm of any signed prefix sum ${\sum }_{i=1}^k{s}_i{t}_i$, $k\in [n]$. In this paper, we analyze the natural Euclidean greedy vector balancing algorithm for this problem: at each step $k$, the sign $s_k\in \{\pm 1\}$ is chosen so that $s_k{t}_k$ has non-positive inner product with ${\sum }_{i=1}^{k-1}{s}_i\cdot t_i$. Our main result is the first finite bound, independent of the sequence length $n$, on the performance of greedy whenever $T$ is finite. When $T\subset {\mathbb{R}}^d$ consists of unit vectors, we prove that the signed sums produced by greedy have Euclidean norm at most $(2/\hat{I}{´}_T{)}^{d-1}$, where $\hat{I}{´}_T$ is the minimum non-zero distance between vectors in $T$ and subspaces spanned by vectors in $T$. The same upper bound holds when the sequences are composed of scaled down vectors in $T$. We also provide a simple set $T$ for which $\hat{I}\text{c◯}(\sqrt{d}/\hat{I}{´}_T)$ is a lower bound. We analyze the greedy algorithm by proving the existence of a bounded convex $K_T$ that is $T$-absorbing: $\forall x\in K_T$ and $t\in \pm T$, $⟨x,t⟩\le 0\Rightarrow x+t\in K_T$. We give an explicit construction of a set $K_T$ contained in a ball of radius $(2/\hat{I}{´}_T{)}^{d-1}$, based on chains of subspaces spanned by vectors in $T$, which may be of independent interest. We generalize our greedy vector balancing bound to online vector partitioning, where the sequence $t_1,\dots ,t_n$ must be partitioned in an online manner into $p$ subsequences. As an application, we prove a special case of a conjecture of Bosman et al. (arxiv:2402.19259), showing that a lexicographic version of total completion time scheduling under scenarios is polynomial time solvable when the number of scenarios is fixed.

21 pages, 3 figures