Flow time scheduling and prefix Beck-Fiala
Flow time scheduling and prefix Beck-Fiala
复制标题
流程时间调度和前缀 Beck-Fiala
DOI：
10.1145/3519935.3520077
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
O. Svensson
中科院分区：
文献类型：
--
作者：
N. Bansal;Lars Rohwedder;O. Svensson
我们将差异理论与最小化最大流动时间和无关机器上的总流动时间的经典调度问题相关。在最佳时间表的流动时间上，将我们的还原与Banaszczyk通过凸几何形状证明的深度结果，可保证O（√logn）和O（√lognlogp）流动时间和总流动时间分别在O（logN）和O（logn logp）的先前最佳保证方面改善。 -Fiala矢量具有稀疏性两个（稀疏性一个是微不足道的），当最大流动时间和总流动时间都会产生严格的保证。条目在{-1,0,1}中以值为单位，我们表明它们不太可能传递到有界ℓ1-摩尔的更通用的2-Sparse情况。
We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded ℓ1-norm) setting to bounds on the flow time of an optimal schedule. Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O(√logn) and O(√logn logP) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O(logn) and O(logn logP). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {−1,0,1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded ℓ1-norm.