Nearly-Tight Bounds for Zonotope Containment and Beyond

Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo, Ruben Skorupinski

arXivarxiv/2605.04183May 5, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.04183
curl -X POST /api/v1/records/arxiv/2605.04183/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.04183/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'