In several practical circumstances we have to solve a problem whose instance is not a priori completely known. Situations of this kind occur in computer systems and networks management, in financial decision making, in robotics etc. Problems that have to be solved without a complete knowledge of the instance are called
. The analysis of properties of on-line problems and the design of algorithmic techniques for their solution (
) have been the subject of intense study since the 70-ies, when classical algorithms for scheduling tasks in an on-line fashion  and for handling paging in virtual storage systems  have been first devised. In the 80-ies formal concepts for analyzing and measuring the quality of on-line algorithms have been introduced  and the notion of
has been defined as the ratio between the value of the solution that is obtained by an on-line algorithm and the value of the best solution that can be achieved by an optimum off-line algorithm that has full knowledge of the problem instance. Since then a very broad variety of on-line problems have been addressed in the literature [14, 19]: memory allocation and paging, bin packing, load balancing in multiprocessor systems, updating and searching a data structure (e.g. a list), scheduling, financial investment, etc.