The sparse zonotope approximation conjecture

About 4 years old · traced to

Let K⊆RdK\subseteq\mathbb{R}^d be a zonotope and let 0<ε≤120<\varepsilon\leq\frac12. A zonotope is a Minkowski sum of finitely many line segments; its number of segments is the number of summands. Sparse zonotope approximation conjecture. There exists a zonotope QQ with O(d/ε2)O(d/\varepsilon^2) segments such that

Q⊆K⊆(1+ε)Q.Q\subseteq K\subseteq(1+\varepsilon)Q.

This is the main open question about approximating a dd-dimensional zonotope by one with only linearly many segments, and it is attributed in the source to the AIM workshop.

References

Primary source

Laurel Heck, Victor Reis and Thomas Rothvoss, “The Vector Balancing Constant for Zonotopes”, arXiv:2210.16460 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.