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 on-line problems. The analysis of properties of on-line problems and the design of algorithmic techniques for their solution (on-line algorithms) have been the subject of intense study since the 70-ies, when classical algorithms for scheduling tasks in an on-line fashion [22] and for handling paging in virtual storage systems [11] have been first devised.