论文标题
流动时间安排和前缀Beck-Fiala
Flow Time Scheduling and Prefix Beck-Fiala
论文作者
论文摘要
我们将差异理论与最小化最大流动时间和无关机器上的总流动时间的经典调度问题联系起来。具体而言，我们给出了一个一般还原，使我们能够在前缀beck-fiala（有限的$ \ ell_1 $ -norm）设置中传输差异界限到最佳时间表的流动时间。 将我们的减少与Banaszczyk通过凸几何形状相结合，并保证$ o（\ sqrt {\ log n}）$和$ o（\ sqrt {\ sqrt {\ log n} \ log log p）的最大流动时间和总数，分别为$ o o（$ o o o o o o） p）$。除了得到改善的保证外，还原还激发了前缀差异问题的看似简单的版本：在前缀Beck-fiala上的任何常数，矢量具有稀疏性二（稀疏性一个是微不足道）的限制，都可以为最大流动时间和总流动时间带来紧张的保证。尽管已知的技术解决了这种情况时，当条目以$ \ { - 1,0,1 \} $中的值进行值时，我们表明它们不太可能将其转移到更通用的$ 2 $ -SPARSE案例的限制$ \ ell_1 $ -norm。
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 $\ell_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(\sqrt{\log n})$ and $O(\sqrt{\log n} \log P)$ for max flow time and total flow time, respectively, improving upon the previous best guarantees of $O(\log n)$ and $O(\log n \log P)$. 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 $\ell_1$-norm.
