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  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 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.
|Titolo:||On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance|
|Data di pubblicazione:||2006|
|Citazione:||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.|
|Appare nelle tipologie:||4.1 Contributo in Atti di convegno|