Constructive Discrepancy Minimization for Convex Sets
Constructive Discrepancy Minimization for Convex Sets
复制标题
凸集的构造性差异最小化
DOI：
10.1137/141000282
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Rothvoss
中科院分区：
文献类型：
--
作者：
T. Rothvoss
Spencer的经典理论表明，任何具有n组和n个元素的集合都可以接受差异O（√（n））事实，Lovett-Meka算法在任何“足够大”的多层中找到了一个不可或缺的积分。至少E-n/500，以下算法在±1：（1）取出一个随机高斯矢量x，（2）计算点y点y∈K∩[-1，1] n点y∈K∩[-1，1] n。在x（3）返回的k∩[-1，1]中。
A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(√(n)). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set K with measure at least e-n/500, the following algorithm finds a point y ∈ K ∩ [-1, 1]n with Ω(n) coordinates in ±1: (1) take a random Gaussian vector x, (2) compute the point y in K ∩ [- 1, 1]n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Giannopoulos.