×

Online computation and competitive analysis. (English) Zbl 0931.68015

Cambridge: Cambridge University Press. xviii, 414 p. (1998).
In contrast to classical optimization algorithms, an online algorithm has to make its decisions online, i.e. with some knowledge on the past, without foreseeing the future, except for some announcements. Decisions have to be made very fast, even in real time, so that completely novel ideas have to be applied. As performance is measured, these are called competitive algorithms or competitive analysis. The examples handled include list accessing, deterministic or randomized paging algorithms, and in a more general setting: game-theoretic foundations, applications in request-answer games, task systems, the \(k\)-server problem (also randomized), load balancing, call admission and circuit routing, search, trading, and portfolio selection, decision theories, and the competitive ratio. The overall appearance of the book, that seems to be very well written, is that of a text explaning much of the material in words with intermediate inequalities or min-max-formulae.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W05 Nonnumerical algorithms
68Q99 Theory of computing
68-02 Research exposition (monographs, survey articles) pertaining to computer science
91A80 Applications of game theory
90C40 Markov and semi-Markov decision processes
91G10 Portfolio theory
PDFBibTeX XMLCite