论文标题
Spencer的定理几乎是输入范围的时间
Spencer's theorem in nearly input-sparsity time
论文作者
论文摘要
Spencer的一个著名定理指出，对于每个集合系统$ S_1，\ dots，s_m \ subseteq [n] $，都有$ \ {\ pm 1 \} $的地面颜色，带有差异$ O（\ sqrt {\ sqrt {n \ log log（n \ log（m/n+2））$。我们提供了一种算法，可以在接近输入sparsity Time $ \ tilde {o}（n+\ sum_ {i = 1}^{m} {m} | s_i |）$中找到这种着色。我们工作中可能具有独立感兴趣的一种关键成分是一种新颖的宽度减小技术，用于求解线性程序，而不是使用乘法权重更新方法在接近输入sparsity的时间内，而不是覆盖/包装类型。
A celebrated theorem of Spencer states that for every set system $S_1,\dots, S_m \subseteq [n]$, there is a coloring of the ground set with $\{\pm 1\}$ with discrepancy $O(\sqrt{n\log(m/n+2)})$. We provide an algorithm to find such a coloring in near input-sparsity time $\tilde{O}(n+\sum_{i=1}^{m}|S_i|)$. A key ingredient in our work, which may be of independent interest, is a novel width reduction technique for solving linear programs, not of covering/packing type, in near input-sparsity time using the multiplicative weights update method.
