On the Power of Randomization in On-Line Algorithms 2: The Bound α∘β Against Adaptive Off-Line Adversaries Is TightResearch Paper
An on-line algorithm must answer each request as it arrives, without knowing the requests to come; paging, caching, the -server problem and metrical task systems are standard examples. Its quality is measured by competitive analysis: its cost is compared with the cost of an optimal off-line solution that knows the whole request sequence. For randomized…