Discrepancy Without Partial Colorings
Discrepancy Without Partial Colorings
复制标题
无局部着色的差异
DOI：
10.4230/lipics.approx-random.2014.258
复制
发表时间：
2014
影响因子：
1
通讯作者：
Mohit Singh
中科院分区：
文献类型：
--
作者：
Nicholas J. A. Harvey;Roy Schwartz;Mohit Singh
斯宾塞定理断言，对于大小为n的基集的n个子集的任何族，基集的元素可以用+1或-1的值“着色”，使得每个集合的和的绝对值为0（√(n)）。这个结果的所有现有证明都递归地构造了“部分着色”，它给一半的基础集赋+1或-1值。我们为斯宾塞定理设计了第一个直接计算着色的算法，而不需要递归地计算部分着色。
Spencer's theorem asserts that, for any family of n subsets of ground set of size n, the elements of the ground set can be "colored" by the values +1 or -1 such that the sum of every set is O(sqrt(n)) in absolute value. All existing proofs of this result recursively construct "partial colorings", which assign +1 or -1 values to half of the ground set. We devise the first algorithm for Spencer's theorem that directly computes a coloring, without recursively computing partial colorings.