{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigd6j3iqnfvhx56mrxt6olbxgmnj5cwbt7ff24mcfgal3dlmz2mfm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mohuqose5my2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.17991v1",
  "publishedAt": "2026-06-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Wojciech Czerwiński",
    "Daniel Dadush",
    "Ekin Ergen",
    "Arka Ghosh",
    "Sławomir Lasota",
    "Łukasz Orlikowski"
  ],
  "textContent": "**Authors:** Wojciech Czerwiński, Daniel Dadush, Ekin Ergen, Arka Ghosh, Sławomir Lasota, Łukasz Orlikowski\n\nIn 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\\\\{\\pm1\\\\}$ in an online manner so as to minimize the largest norm of any signed prefix sum $\\sum_{i=1}^ks_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\\\\{\\pm1\\\\}$ 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/δ_T)^{d-1}$, where $δ_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 $Ω(\\sqrt{d}/δ_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$, $\\langle x,t\\rangle\\leq0\\Rightarrow x+t\\in K_T$. We give an explicit construction of a set $K_T$ contained in a ball of radius $(2/δ_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.",
  "title": "Greedy Vector Balancing"
}