Online Algorithms with Advice for Bin Packing and Scheduling Problems

Abstract

We consider the setting of online computation with advice, and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of $1$ with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is $(1+\epsilon )$-competitive and uses $O\left(\frac{1}{\epsilon }\log \frac{1}{\epsilon }\right)$ bits of advice per request. For scheduling on $m$ identical machines, with the objective function of any of makespan, machine covering and the minimization of the ${\ell }_p$ norm, $p>1$, we give similar results. We give online algorithms with advice which are $(1+\epsilon )$-competitive ($(1/(1-\epsilon ))$-competitive for machine covering) and also use $O\left(\frac{1}{\epsilon }\log \frac{1}{\epsilon }\right)$ bits of advice per request. We complement our results by giving a lower bound showing that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a non-constant number (namely, at least $\left(1-\frac{2m}{n}\right)\log m$, where $n$ is the number of jobs and $m$ is the number of machines) of bits of advice per request is needed.

20 pages

Cited by in corpus (3)

• Optimal Online Edge Coloring of Planar Graphs with Advice
• Weighted Online Problems with Advice
• The Advice Complexity of a Class of Hard Online Problems