Online Makespan Scheduling with Sublinear Advice
Dohrau, Jérôme · Repository for Publications and Research Data (ETH Zurich) · 2013
We study online makespan scheduling with a fixed number of parallel machines. Jobs arrive in an online fashion in consecutive time steps, and must be scheduled both immediately and definitely. In contrast to the number of machines, the number of jobs is not known in advance. This paper focuses on the advice complexity of the problem. Basically, we ask how much additional information may help us to obtain solutions of high quality. Our main result is the construction of a (1 + e)-competitive online algorithm with advice that reads a constant number of advice bits, for any e > 0; here, “constant” means with respect to the input size, but our bound does depend on the number of machines and e. This result is particularly interesting since it shows some very significant threshold behavior; it is known that, to be a little better, namely optimal, a linear number of advice bits is necessary. We also show that the advice can be derived from the input in polynomial time (with respect to the input size).