A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
复制标题
DOI：
10.1137/1.9781611973105.9
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Elisabeth Günther;O. Maurer;Nicole Megow;Andreas Wiese
中科院分区：
文献类型：
--
作者：
Elisabeth Günther;O. Maurer;Nicole Megow;Andreas Wiese
通过引入竞争比近似方案的新概念，提出了一种在线调度中竞争分析的新方法。这样的方案在算法上构造具有任意接近于任何在线算法的最佳可能竞争比的竞争比的在线算法。我们研究的问题调度作业在线，以尽量减少加权和的完成时间的并行，相关和不相关的机器，我们得出确定性和随机算法，这几乎是最好的所有在线算法的各自的设置。我们还推广我们的技术，任意单项成本函数，并将其应用到最大完工时间目标。我们的方法依赖于在线算法的抽象表征，结合各种简化和变换。我们还贡献算法手段来计算的实际价值的最佳可能的竞争力的比率高达任意精度。这强烈对比（几乎）所有以前手动获得的竞争力结果，最重要的是，它减少了对最佳竞争比的搜索，计算机可以回答的问题。我们相信，我们的概念也可以应用到许多其他问题，并产生一个新的角度在线算法一般。
We propose a new approach to competitive analysis in online scheduling by introducing the novel concept of competitive-ratio approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also generalize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts (nearly) all previous manually obtained competitiveness results and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our concept can also be applied to many other problems and yields a new perspective on online algorithms in general.