Fair Scheduling via Iterative Quasi-Uniform Sampling
Fair Scheduling via Iterative Quasi-Uniform Sampling
复制标题
DOI：
10.1137/1.9781611974782.171
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
Sungjin Im;Benjamin Moseley
中科院分区：
文献类型：
--
作者：
Sungjin Im;Benjamin Moseley
在本文中，我们考虑最小化的lk-范数的流时间在一台机器上离线使用抢占式调度，k ≥ 1。我们展示了该问题的第一个O（1）近似，改进了Bansal和Pruhs（FOCS 09和SICOMP 14）以前的最佳O（log log P）近似，其中P是最大作业大小与最小作业大小之比。我们的主要技术成分是一种新的准均匀采样和迭代舍入的组合，这是在其本身的权利感兴趣。
In the paper we consider minimizing the lk-norms of flow time on a single machine offline using a preemptive scheduler for k ≥ 1. We show the first O(1)-approximation for the problem, improving upon the previous best O(log log P)-approximation by Bansal and Pruhs (FOCS 09 and SICOMP 14) where P is the ratio of the maximum job size to the minimum. Our main technical ingredient is a novel combination of quasi-uniform sampling and iterative rounding, which is of interest in its own right.