论文标题
遗传保证的快速差异最小化
Fast Discrepancy Minimization with Hereditary Guarantees
论文作者
论文摘要
自班萨尔（Bensal）的突破性工作（2010年）以来，已经对各种集合系统的低差异着色有效地进行了研究，后者为多种重要设置提供了第一个多项式时间算法，包括通用集合系统，稀疏集合系统，稀疏集体系统以及具有有界遗传性遗传性遗传性差异的SET系统。设定系统的遗传差异是可通过删除接地元素的子集获得的所有设定系统的最大差异。虽然是多项式时间，但班萨尔的算法并不实用，例如他的世袭设置算法在时间$ω（M n^{4.5}）$上运行，用于$ m $ set的设置系统，上面是一组$ n $元素。此后，为一般和稀疏的集合系统开发了更有效的算法，但是，对于世袭案例，班萨尔的算法仍然是最先进的。在这项工作中，我们给出了遗传保证的更快算法，以$ o（Mn^2 \ lg（2 + m/n） + n^3）$时间运行。我们的算法基于对具有界面遗传差异的固定系统的新结构见解。我们还实施了算法，并在实验上表明，它计算出明显好于随机的颜色，并且在合理的时间内完成，即使在设置系统上，在成千上万个元素的地面集上都有数千组。
Efficiently computing low discrepancy colorings of various set systems, has been studied extensively since the breakthrough work by Bansal (FOCS 2010), who gave the first polynomial time algorithms for several important settings, including for general set systems, sparse set systems and for set systems with bounded hereditary discrepancy. The hereditary discrepancy of a set system, is the maximum discrepancy over all set systems obtainable by deleting a subset of the ground elements. While being polynomial time, Bansal's algorithms were not practical, with e.g. his algorithm for the hereditary setup running in time $Ω(m n^{4.5})$ for set systems with $m$ sets over a ground set of $n$ elements. More efficient algorithms have since then been developed for general and sparse set systems, however, for the hereditary case, Bansal's algorithm remains state-of-the-art. In this work, we give a significantly faster algorithm with hereditary guarantees, running in $O(mn^2\lg(2 + m/n) + n^3)$ time. Our algorithm is based on new structural insights into set systems with bounded hereditary discrepancy. We also implement our algorithm and show experimentally that it computes colorings that are significantly better than random and finishes in a reasonable amount of time, even on set systems with thousands of sets over a ground set of thousands of elements.
