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

G. Ausiello, L. Allulli, V. Bonifaci, L. Laura

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

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 . 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.
Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation (Proceedings Third International Conference, TAMC'06, Beijing, China, May 15-20, 2006)
EditorsJ.-Y. Cau, B.S. Cooper, A. Li
Place of PublicationBerlin
PublisherSpringer
Pages1-20
ISBN (Print)3-540-34021-1
DOIs
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
Volume3959
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'On-line algorithms, real time, the virtue of laziness, and the power of clairvoyance'. Together they form a unique fingerprint.

Cite this