Constructing Randomized Online Algorithms from Algorithms with Advice

Abstract

In the model of advice complexity for online problems, an online algorithm is amended by an advice tape prepared by an oracle that knows the whole input in advance, and it is measured how many bits from this tape an online algorithm has to read in order to reach a certain solution quality. This model was introduced and successfully applied as a means for an improved analysis of the hardness of online problems. It was shown that it has strong connections to randomized computations, e. g., lower bounds on the advice complexity can be used to prove lower bounds also on randomized algorithms. In this paper, we complement these known results with a method for constructing randomized online algorithms from online algorithms with advice. More precisely, we consider task systems, which model many well-known online problems such as paging, k-server, ski rental, etc. For these problems, we show how to transform any online algorithm using a small amount of advice into a randomized algorithm with almost the same competitive ratio. We achieve this by using methods from algorithmic learning theory. Using this result, we furthermore show how to translate lower bounds on randomized online computations into lower bounds for the advice complexity.