论文标题
矢量平衡常数
The Vector Balancing Constant for Zonotopes
论文作者
论文摘要
两个对称凸形$ k，q $的矢量平衡常数$ \ mathrm {vb}（k，q）$是最小$ r \ geq 0 $，因此，从$ k $的任何数量的向量都可以平衡为$ r $ $ r $ scaling $ q $ $ q $。 Schechtman提出的一个问题是，对于任何Zonotope $ k \ subseteq \ mathbb {r}^d $一个一个具有$ \ mathrm {vb}（k，k，k）\ sellsim \ sqrt {d} $。直观地，这询问Spencer定理（$ k = b^d_ \ infty $）是否具有自然的几何概括。我们证明，对于任何Zonotope $ k \ subseteq \ Mathbb {r}^d $一个一个具有$ \ mathrm {vb}（k，k）\ simsim \ sqrt {d} \ log \ log \ log \ log \ log \ log \ log \ log \ log \ d $。我们的主要技术贡献是对归一化界限的任何部分的高斯度量的紧密下限，从而将Vaaler的定理推广为立方体的定理。我们还证明，对于两个不同的归一化型技术，$ k $和$ q $一个具有$ \ mathrm {vb}（k，q）\ lyseSim \ sqrt {d \ log log d} $。所有边界都是建设性的，可以在多项式时间内计算相应的着色。
The vector balancing constant $\mathrm{vb}(K,Q)$ of two symmetric convex bodies $K,Q$ is the minimum $r \geq 0$ so that any number of vectors from $K$ can be balanced into an $r$-scaling of $Q$. A question raised by Schechtman is whether for any zonotope $K \subseteq \mathbb{R}^d$ one has $\mathrm{vb}(K,K) \lesssim \sqrt{d}$. Intuitively, this asks whether a natural geometric generalization of Spencer's Theorem (for which $K = B^d_\infty$) holds. We prove that for any zonotope $K \subseteq \mathbb{R}^d$ one has $\mathrm{vb}(K,K) \lesssim \sqrt{d} \log \log \log d$. Our main technical contribution is a tight lower bound on the Gaussian measure of any section of a normalized zonotope, generalizing Vaaler's Theorem for cubes. We also prove that for two different normalized zonotopes $K$ and $Q$ one has $\mathrm{vb}(K,Q) \lesssim \sqrt{d \log d}$. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.
