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. In the 80-ies formal concepts for analyzing and measuring the quality of on-line algorithms have been introduced [40] and the notion of competitive analysis 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.
Ausiello, G., Allulli, L., Bonifaci, V., Laura, L. (2006). On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance. In Proc. 3rd Int. Conf. on Theory and Applications of Models of Computation (pp.1-20). Berlin : Springer Verlag [10.1007/11750321_1].
On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance
Bonifaci V.;
2006-01-01
Abstract
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. In the 80-ies formal concepts for analyzing and measuring the quality of on-line algorithms have been introduced [40] and the notion of competitive analysis 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
