(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Measuring On-Line Algorithms using the Cooperative Ratio

Alex López-Ortiz
School of Computer Science
University of Waterloo

Tuesday, February 12, 2008, at 14:15
IMADA's Seminar Room

ABSTRACT

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)

 


   Data protection at SDUDatabeskyttelse på SDU