A somewhat informal term, an algorithm is called "online" if it produces (partial) output while still reading its input. Some algorithms must be online, because they produce a stream of output for a stream of input; output is produced while the input (which might even be infinite in length) is being read.

All scheduling algorithms are online algorithms. In the context of scheduling, the concept of "per-operation complexity" is particularly important. When an OS is paging memory, or when a dispatcher is dispatching ambulances around the city, it is often important to be able to guarantee certain levels of performance. And, of course, the OS or dispatcher have no idea what happens next: they must decide strictly according to data available at the time of the action taken.. Worst case performance, amortized performance and various probabilistic measures (such as expected performance) are all important here.

But even outside of scheduling, it makes sense to consider online algorithms. Online algorithms are often harder than their offline correspondents:


With the death of the Net in 2001, online algorithms have again achieved the respectability which they lost to Web Services earlier. This short commercial message from the Computational Complexity Coalition brought to you by the marketing slogan "Mallinking makes us strong".

An online algorithm will never be better than the corresponding offline or "omniscient" algorithm -- an algorithm faced with the same problem, which for any input stream "guesses" the optimal output at every step. This is because at the very least the offline version could simulate having to return output prematurely, given partial input. But how to measure the (decreased) performance of an online algorithm?

Sometimes, a probabilistic model of the input is available, and the goal is to minimise the expected cost (or maximise the expected return, or whatever you measure the offline version by). But what if you have no probabilistic model?

The answer recently popular in computer science is "competitive analysis": an online algorithm is said to be c-competitive, if it is never more than c times as bad as the best (optimal) offline version. If you lack a probabilistic model, this is a good estimate, in line with the worst case or "adverserial" model favoured in much of computer science. The smaller your c, the better. A typical goal of computer scientists in this field is to find a c-competitive online algorithm, and prove that c to be the best possible. (But note that sometimes, there is no c-competitive solution at all, for any c!)

The absolute standard introductory online algorithm problem is the Ski Rental Problem: you're on your first-ever ski holiday, and you have no idea how many times you'll want to go skiing; every morning you must decide, should you buy your own skis (for $150) or rent them for one day (for $10)? (Your goal is to minimise total expenditure). The answer, although simple, gives a feel for some of the field's quirks and surprises. But give the problem description a go before you head for the spoiler.

Here are two other instructive problems in similar vein. Consider them at your leisure...

  1. You've lost your spectacles somewhere along the beach, right by the water. As a result, you can only actually see them if you're right next to them. They could be anywhere along the beach (which stretches north and south, infinitely). What path should you take along your search, to minimise the total distance walked? (The optimal algorithm, given the actual location of the spectacles, is trivial).
  2. You are offered a succession of predetermined (but unknown to you) cash prizes. When each sum is offered, you may take the prize (ending the game), or decline it and proceed to the next offer. What strategy should you adopt?

In the real world™, online algorithms are often considered in the context (or pretext?) of load balancing problems, where a resource or resources must be allocated to (dependent or independent) tasks of varying cost and profitability. These have applications in communications and other lucrative businesses. The simpler scenarios are well studied, but many important problems are still open.

Log in or register to write something here or to contact authors.