On-Line Algorithms Versus Off-Line Algorithms: How Much Is It Worth to Know the Future?
Title | On-Line Algorithms Versus Off-Line Algorithms: How Much Is It Worth to Know the Future? |
Publication Type | Technical Report |
Year of Publication | 1992 |
Authors | Karp, R. M. |
Other Numbers | 749 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf |
Bibliographic Notes | ICSI Technical Report TR-92-044 |
Abbreviated Authors | R. M. Karp |
ICSI Publication Type | Technical Report |