{"id":"arxiv/2605.04183","url":"https://arxiv.org/abs/2605.04183","tags":["cs.DS","math.MG"],"score":0,"title":"Nearly-Tight Bounds for Zonotope Containment and Beyond","domain":"cs.DS","source":"arxiv","authors":["Friedrich Eisenbrand","Thomas Rothvoss","Matteo Russo","Ruben Skorupinski"],"reviews":0,"subject":"cs.DS","summary":"We investigate the convex-body containment problem $\\max\\{s >0 : s Z \\subseteq Q\\}$, where the outer body $Q \\subseteq \\mathbb R^d$ is described by a membership oracle and the inner body $Z \\subseteq \\mathbb R^d$ is a zonotope. Our main result is a sampling-based $O(\\sqrt{d})$-approximation algorithm for this problem that almost matches the lower bound of $Ω(\\sqrt{d/\\log d})$ by Khot and Naor in the oracle model. Assuming zonotopes can be sparsified by a linear number of generators, which is referred to as Talagrand conjecture, our approach attains the optimal approximation factor of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-05","reactions":{}}