论文标题
通过自我平衡步行最小化差异
Discrepancy Minimization via a Self-Balancing Walk
论文作者
论文摘要
我们在各种设置下研究$ \ mathbb {r}^n $中向量的差异最小化。主要结果是通过比较参数在多个维度中对新的简单随机过程进行分析。作为推论，我们获得了与Bansal，Jiang，Singla和Sinha构成的在线矢量平衡的几个问题的界限（Stoc 2020），以及对于Komlós推测的对数界限的线性时间算法。
We study discrepancy minimization for vectors in $\mathbb{R}^n$ under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for several problems in online vector balancing posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as linear time algorithms for logarithmic bounds for the Komlós conjecture.
