On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance

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 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 fashion [22] and for handling paging in virtual storage systems [11] have been first devised. In the 80-ies formal concepts for analyzing and measuring the quality of algorithms have been introduced [40] and the notion of has been defined as the ratio between the value of the solution that is obtained by an algorithm and the value of the best solution that can be achieved by an optimum algoritm that has full knowledge of the problem instance. Since then a very broad variety of 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.