Bibliographic Details
| Title: |
BEYOND COMPETITIVE ANALYSIS. |
| Authors: |
Koutsoupias, Elias, Padadimitriou, Christos H. |
| Source: |
SIAM Journal on Computing. 2000, Vol. 30 Issue 1, p300. 18p. |
| Subjects: |
Online algorithms, Paging (Computer science), Decision making, Computer science |
| Abstract: |
The competitive analysis of online algorithms has been criticized as being too crude and unrealistic. We propose refinements of competitive analysis in two directions: The first restricts the power of the adversary by allowing only certain input distributions, while the other allows for comparisons between information regimes for online decision-making. We illustrate the first with an application to the paging problem; as a byproduct we characterize completely the work functions of this important special case of the k-server problem. We use the second refinement to explore the power of lookahead in server and task systems. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
