E. Koutsoupias and C. Papadimitriou.
Beyond competitive analysis.
SIAM Journal on Computing, 30(1):300--317, 2000.
Abstract
The competitive analysis of on-line 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 on-line 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.Bib
@Article{KP00,
author = {E. Koutsoupias and C. H. Papadimitriou},
title = {Beyond competitive analysis},
journal = {SIAM Journal on Computing},
year = {2000},
volume = {30},
number = {1},
pages = {394--400}
}
@string{FOCS94 = {Proceeding 35th Annual Symposium on Foundations of
Computer Science}}
@InProceedings{KP94b,
author = {E. Koutsoupias and C. H. Papadimitriou},
title = {Beyond competitive analysis},
booktitle = FOCS94,
year = 1994,
month = {20--22 } # nov,
pages = {394--400},
address = {Santa Fe, New Mexico},
note = {Final version in Siam J. on Comp.}
}