{"id":"arxiv/2609.20238","url":"https://arxiv.org/abs/2609.20238","tags":["cs.DS","math.MG"],"score":0,"title":"Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms","domain":"cs.DS","source":"arxiv","authors":["Arpon Basu","Joshua Brakensiek","Yeyuan Chen","Aaron Putterman","Victor Reis","Zihan Zhang"],"reviews":0,"subject":"cs.DS","summary":"We extend the recent work of Reis and Rothvoss on sparsifying sums of $\\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\\varepsilon > 0$ and centrally symmetric, convex sets $C_1, \\ldots, C_m\\subseteq\\mathbb{R}^n$ there is a choice of weights $λ_1, \\dots , λ_m \\in \\mathbb{R}_{\\geq 0}$ such that at most $O(n / \\varepsilon^2)$ of the weights are non-zero, and \\[(1 - \\varepsilon)\\cdot C\\subseteq\\sum_{i = 1}^mλ_i\\cdot C_i\\subseteq(1 + \\varepsilon)\\cdot C,\\] where $C:= C_1 + \\cdots + C_m$ refers…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}