Publication Details
Title: On-Line Algorithms Versus Off-Line Algorithms: How Much Is It Worth to Know the Future?
Author: R. M. Karp
Group: ICSI Technical Reports
Date: July 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-044
Bibliographic Reference:
R. M. Karp. On-Line Algorithms Versus Off-Line Algorithms: How Much Is It Worth to Know the Future?. ICSI Technical Report TR-92-044, July 1992
Author: R. M. Karp
Group: ICSI Technical Reports
Date: July 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-044
Bibliographic Reference:
R. M. Karp. On-Line Algorithms Versus Off-Line Algorithms: How Much Is It Worth to Know the Future?. ICSI Technical Report TR-92-044, July 1992