Knowledge States: A Tool for Randomized Online Algorithms
Wolfgang W. Bein, Lawrence L. Larmore, Rüdiger Reischuk · 2008
We introduce the concept of knowledge states; many well-known randomized online algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory. A knowledge state simply states conditional obligations of an adversary, by fixing an estimator function, and gives a distribution for the algorithm. When a knowledge state algorithm receives a request, it then calculates one or more “subsequent” knowledge states, together with a probability of transition to each. The algorithm then uses randomization to select one of those subsequents to be the new knowledge state.