← All problems

The sparse zonotope approximation conjecture

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
  1. 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.