Online Makespan Scheduling with Sublinear Advice

Abstract

Online algorithms are of importance for many practical applications. Typical examples involve scheduling and routing algorithms employed in operating systems and computer networks. Beside their practical signicance, online algorithms are extensively studied from a theoretical point of view. Due to the nature of online problems, these algorithms fail to be optimal in general. The quality of their output is usually measured by the so called competitive ratio. A few years ago, another measure, the advice complexity, has been introduced to give a deeper insight into the nature of an online problem and to capture the essential information contained in the instances of the problem.<br/>The makespan scheduling problem is a generic scheduling problem where the task is to schedule jobs with dierent processing times on identical machines. The objective is to distribute the processing times as evenly as possible among the machines. This is why this problem is sometimes referred to as the load balancing problem. When considering the online version of the problem, the jobs arrive gradually and have to be assigned to a machine immediately at their arrival. In the work at hand, we study the advice complexity of the online makespan scheduling problem restricted to two machines.<br/>For this problem it proves to be that already little advice helps a great deal to improve the competitive ratio in comparison to purely deterministic online algorithms. Therefore, this work mainly focuses on upper bounds. First, we give linear upper and lower bounds on the advice complexity for optimal algorithms with advice, with the bounds being tight up to one bit. Afterwards, we introduce a very simple online algorithm with logarithmic advice complexity and a competitive ratio of 4 3 . We also show that with a more involved strategy an online algorithm can get arbitrarily close to this competitive ratio using only a constant number of advice bits. As the main result we prove that even a constant number of advice bits is sucient to achieve an almost optimal solution.