On randomization in on-line computation

Reviewer: Stefan Corneliu V. Stefanescu

We conceptually think at a randomized algorithm having often in mind a computation tree where in its nodes we take randomly decisions. From another point of view we can define randomized algorithms considering random input data or imposing any other probabilistic actions on deterministic algorithms. These two aspects seem to have something in common with behavioral and mixed strategies regarding the game theoretic concepts. This kind of connection was made in this article. So, in the paper is defined the notion of deterministic on-line algorithm as a sequence of functions having given properties. The off-line algorithms are also regarded as functions which are used to introduce the concept regarding the off-line optimal algorithm. Having these abstract notions becomes possible to speak about C-competitive properties for deterministic on-line algorithms. The generalization concerning the aspects about the randomized algorithms is based on two prominent approaches: one which operates with mixed strategies and another one based on behavioral strategies. The new definitions are used in the paper to design and analyze the randomized online algorithms. The basic results, taken over especially from the game theory, are constructively applied in the new context of on-line computation. So it is suggested how to adjust the known Yao principle__?__of the game theory. In the paper are also discussed aspects concerning the lower bounding competitive ratios of randomized on-line algorithms (for profit maximization and for cost minimization problems too). An interesting approach concerns the conditions of equivalence between the different kinds of randomization connected to the facts from the game theory. An example to distinguish between two type of randomization is also given. In particular it is shown that mixed randomized memoryless paging algorithms can achieve strictly better competitive performance than behavioral randomized procedures. At the end of the paper there are suggested several directions for a future research (for example to select more suitable models from games involving memory algorithms).