CONSTRUCTIVE DISCREPANCY MINIMIZATION BY WALKING ON THE EDGES
CONSTRUCTIVE DISCREPANCY MINIMIZATION BY WALKING ON THE EDGES
复制标题
DOI：
10.1137/130929400
复制
发表时间：
2015-01-01
影响因子：
1.6
通讯作者：
Meka, Raghu
中科院分区：
文献类型：
--
作者：
Lovett, Shachar;Meka, Raghu
最小化设定系统的差异是组合学中的一个基本问题。该地区的基石之一是Spencer的六个标准偏差[Trans。阿米尔。数学。 Soc。，289（1985），第679-706页]：在N大小为N的n组系统中，始终存在着具有差异6 root n的着色。 Spencer的原始证明在本质上是存在的，没有提供有效的算法来找到这种着色。最近，班萨尔（Bansal）的一项突破性作品[FOCS，2010年，第3-10页]给出了一种有效的算法，发现了这种着色。他的算法是基于对差异问题和巧妙的圆形程序放松的SDP放松。在这项工作中，我们给出了一种新的随机算法，以根据Spencer的结果找到着色，基于限制的随机步行，我们称之为边缘步行。我们的算法及其分析仅使用基本的线性代数，并且确实是建设性的，因为它不吸引生存论点，提供了Spencer定理和部分着色引理的新证明。
Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer [Trans. Amer. Math. Soc., 289 (1985), pp. 679-706]: In any system of n sets in a universe of size n, there always exists a coloring which achieves discrepancy 6 root n. The original proof of Spencer was existential in nature and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal [Proceedings of FOCS, 2010, pp. 3-10] gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencer's result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is truly constructive in that it does not appeal to the existential arguments, giving a new proof of Spencer's theorem and the partial coloring lemma.