论文标题
通过迭代公平争夺解决方案，无关机器的加权完成时间最小化
Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
论文作者
论文摘要
对于经典的调度问题，我们提供了1.488- approximation，以最大程度地减少无关机器上的总加权完成时间。这是$（1.5-10^{ - 7}）$ - 近似值（Stoc 2016，Bansal-Srinivasan-Svensson）的$（1.5-10^{ - 7}）的突破，以及$（1.5-1/6000）$ - 近似值（FOCS 2017，LI）的后续结果。 Bansal等。引入了一种新颖的四舍五入方案，该方案首次产生了强大的负相关性，并将其应用于计划问题以获得其突破，如果人们可以基于独立的圆形，可以击败长期存在的$ 1.5 $ approximation屏障，从而解决了开放问题。我们的关键技术贡献是通过迭代公平争夺解决方案实现更强大的负相关性，这具有独立的利益。以前，Bansal等。通过各种移动式舍入的变体获得了强大的负相关性，并将其用作黑匣子。
We give a 1.488-approximation for the classic scheduling problem of minimizing total weighted completion time on unrelated machines. This is a considerable improvement on the recent breakthrough of $(1.5 - 10^{-7})$-approximation (STOC 2016, Bansal-Srinivasan-Svensson) and the follow-up result of $(1.5 - 1/6000)$-approximation (FOCS 2017, Li). Bansal et al. introduced a novel rounding scheme yielding strong negative correlations for the first time and applied it to the scheduling problem to obtain their breakthrough, which resolved the open problem if one can beat out the long-standing $1.5$-approximation barrier based on independent rounding. Our key technical contribution is in achieving significantly stronger negative correlations via iterative fair contention resolution, which is of independent interest. Previously, Bansal et al. obtained strong negative correlations via a variant of pipage type rounding and Li used it as a black box.
