IMADA - Department of Mathematics and Computer Science |
In this talk we first give an overview of the general shortcomings of the competitive ratio as a model for on-line analysis in the case of on-line paging algorithms. Then we introduce a technique that solves a long standing open problem in the field of developing a natural model for online paging, with no pre-ordained knowledge of the request sequence, which could separate algorithms which are not equivalent in practice. Lastly we introduce a generalization of this model which is applicable in various on-line settings and does not suffer from the drawbacks of competitive analysis. This is joint work with Spyros Angelopoulos, Reza Dorrigiv, and Martin Ehmsen. Host: Kim Skak Larsen SDU HOME | IMADA HOME | Previous Page Last modified: Fri Feb 1 11:16:07 CET 2008 Joan Boyar (joan@imada.sdu.dk) |