On-Line Algorithms: How Much Is It Worth to Know the Future?

In an on­line problem, the input is obtained incrementally over time. An on­line algorithm makes a sequence of decisions, where each decision is based only on the partial input obtained until that time, without knowledge of future input. Some on­line algorithms make decisions as soon as new data becomes available. But there are other on­line algorithms with lookahead, i.e. they obtain partial information about future input by possibly delaying their decision at some extra cost. The question is, when and how much does it help to have more information about the future? In this note, we
survey some of the well known problems studied in the on­line context and summarize performance guarantees of on­line algorithms with and without lookahead. For some of the problems, we observe that a substantial amount of lookahead is required to obtain an improvement in the competitive ratio of any on­line algorithm. We have also observed that the influence of lookahead depends on the choice of the objective function and on the model of lookahead used for each problem. Finally, for certain problems, measuring the performance of on­line algorithms by alternative measures other than the competitive ratio may reflect the influence of lookahead on performance better.