论文标题
改进了无关机器调度的近似值
Improved Approximations for Unrelated Machine Scheduling
论文作者
论文摘要
我们在无关的机器设置中重新审视两个经过深入研究的调度问题，每个作业都可以在每台机器上都有不同的处理时间。为了最大程度地减少总加权完成时间，我们给出了1.45- approximation，这在先前的1.488-Approximation [IM和Shadloo Soda 2020]中改善。这种改进的关键技术成分在于一种新的四舍五入方案，该方案与限制更少的限制更加牢固。为了最大程度地减少$ l_k $ - 机器负载的数量，灵感来自[Kalaitzis等人。 SODA 2017]，我们提供更好的近似算法。特别是，我们给出了$ \ sqrt {4/3} $ - $ l_2 $ - norm的近似值，该近似是由于[Azar-Epstein STOC 2005]和[Kumar等人而改善了以前的$ \ sqrt 2 $ approximations。 JACM 2009]。
We revisit two well-studied scheduling problems in the unrelated machines setting where each job can have a different processing time on each machine. For minimizing total weighted completion time we give a 1.45-approximation, which improves upon the previous 1.488-approximation [Im and Shadloo SODA 2020]. The key technical ingredient in this improvement lies in a new rounding scheme that gives strong negative correlation with less restrictions. For minimizing $L_k$-norms of machine loads, inspired by [Kalaitzis et al. SODA 2017], we give better approximation algorithms. In particular we give a $\sqrt {4/3}$-approximation for the $L_2$-norm which improves upon the former $\sqrt 2$-approximations due to [Azar-Epstein STOC 2005] and [Kumar et al. JACM 2009].
