Susanne Albers: Competitive Analysis and Beyond
Channel: Stanford Computer Science Theory
Date: 2011-10-16

Videos from the Beyond Worst Case Analysis Workshop 
Stanford, CA; Sept 19-21, 2011 
http://theory.stanford.edu/~tim/bwca/bwca.html

Susanne Albers: Competitive Analysis and Beyond

In the design of online algorithms standard competitive analysis can lead to overly pessimistic performance guarantees. In the first part of this talk we will review various techniques to overcome such negative results. In the second part we will study list update, a cornerstone problem in the theory of online algorithms. We introduce a new model of locality of reference. Using this model we present a combined theoretical and experimental study in which the theoretically proven and experimentally observed performance guarantees match or nearly match.