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

An "on-line algorithm" is one that receives a sequence of requests and performs an immediate action in response to each request. On-line algorithms arise in any situation where decisions must be made and resources allocated without knowledge of the future. The effectiveness of an on-line algorithm may be measured by its "competitive ratio", defined as the worst-case ratio between its cost and that of a hypothetical off-line algorithm which knows the entire sequence of requests in advance and chooses its actions optimally. In a variety of settings, we discuss techniques for proving upper and lower bounds on the competitive ratios achievable by on-line algorithms. In particular, we discuss the advantages of randomized on-line algorithms over deterministic ones.

ICSI Technical Report TR-92-044

Technical Report