# Online Algorithms with Advice for Bin Packing and Scheduling Problems

arXiv: https://arxiv.org/abs/1311.7589 · HTML: https://mlsanity.com/paper/1311.7589/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2013.

## Built on by (most cited first, 1 of 1)

- [Machine Learning-Enhanced Ant Colony Optimization for Column Generation](https://mlsanity.com/paper/2407.01546/) (2024)

## Abstract (arXiv)

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+varepsilon)-competitive and uses Oleft(frac1varepsilonlog frac1varepsilon 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 ℓp norm, p >1, we give similar results. We give online algorithms with advice which are (1+varepsilon)-competitive ((1/(1-varepsilon))-competitive for machine covering) and also use Oleft(frac1varepsilonlog frac1varepsilon 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 - frac2mnright)log m, where n is the number of jobs and m is the number of machines) of bits of advice per request is needed.