论文标题
差异，匹配和近似值的算法：快速，简单和实用
Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical
论文作者
论文摘要
我们研究数据近似和优化中的关键工具之一：低分配着色。正式地，给定有限集系统$（x，\ nathcal s）$，两个两色$χ：x \ to \ x \ to \ x \ to \ { - 1,1 \} $的\ emph {vivepancy}定义为$ \ axmag_ {s \ in \ mathcal s}}} \在s}χ（x）$中。 我们提出了一个随机算法，对于任何$ d> 0 $和$（x，\ \ nathcal s）$，带双重粉碎功能$π^*（k）= o（k^d）$，返回具有预期差异$ o \ o \ lest（{\ sqrt {\ sqrt {| x | x |^|^| | | | | | | | | |随着时间的推移）$ \ tilde o \ left（{| \ Mathcal s | \ cdot | x |^{1/d}+| x | x |^{2+1/d}}} \ right）$，在$ \ lest的先前最佳时间（| \ nathcal s | frirt）c. $ | x |^{2-1/d} $当$ | \ Mathcal S | \ geq | x | $。该设置包括许多几何类别，有界双VC维度的家族等等。直接的结果，我们获得了一种改进的算法来构建子分数大小的$ \ varepsilon $ approximations。 我们的方法通过对随机更新的权重进行了改进的分析，并通过较低的交叉数 - 计算几何形状的基本结构来利用原始偶的重新尊重。特别是，我们得到相同的$ | x |^{2-1/d} $ factor factor factor factor factor facter of匹配时间，交叉数字$ o \ left（{| x |^|^{1-1/d}} \ right）$，这是自1980年代以来的第一个改进。 所提出的算法非常简单，这使得第一次有可能以几乎最佳的差异计算颜色，并且在尺寸高于$ 2 $的尺寸的抽象和几何套装系统中，对于抽象和几何套装系统的近似近似值。
We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system $(X,\mathcal S)$, the \emph{discrepancy} of a two-coloring $χ:X\to\{-1,1\}$ is defined as $\max_{S \in \mathcal S}|{χ(S)}|$, where $χ(S)=\sum\limits_{x \in S}χ(x)$. We propose a randomized algorithm which, for any $d>0$ and $(X,\mathcal S)$ with dual shatter function $π^*(k)=O(k^d)$, returns a coloring with expected discrepancy $O\left({\sqrt{|X|^{1-1/d}\log|\mathcal S|}}\right)$ (this bound is tight) in time $\tilde O\left({|\mathcal S|\cdot|X|^{1/d}+|X|^{2+1/d}}\right)$, improving upon the previous-best time of $O\left(|\mathcal S|\cdot|X|^3\right)$ by at least a factor of $|X|^{2-1/d}$ when $|\mathcal S|\geq|X|$. This setup includes many geometric classes, families of bounded dual VC-dimension, and others. As an immediate consequence, we obtain an improved algorithm to construct $\varepsilon$-approximations of sub-quadratic size. Our method uses primal-dual reweighing with an improved analysis of randomly updated weights and exploits the structural properties of the set system via matchings with low crossing number -- a fundamental structure in computational geometry. In particular, we get the same $|X|^{2-1/d}$ factor speed-up on the construction time of matchings with crossing number $O\left({|X|^{1-1/d}}\right)$, which is the first improvement since the 1980s. The proposed algorithms are very simple, which makes it possible, for the first time, to compute colorings with near-optimal discrepancies and near-optimal sized approximations for abstract and geometric set systems in dimensions higher than $2$.
