Information is perhaps the most important ingredient for all computationaltasks. It is generally true that the more input information is given, thebetter algorithmic performance one can expect.
Don't we all have experiences with such scenarios? Have you ever wonderedwhether to hold onto your IBM stocks or sell them now? Should you pay $700dollars to join a fitness club for a year or pay $5 dollars per visit?Should your virtual memory management strategy keep a page in the cacheor replace it right away? The common denominator of such problems is theconstraint that one must maka decisions without complete information.
This book concerns the problem of computing with incomplete information.In particular, it focuses on a common scenario where the input is givenone piece at a time, and upon receiving an input, the algorithm must takean irreversible action without the knowledge of future inputs. That is,once an action is taken, either we cannot undo it at all or the undoingwill incur a cost, which adversely affects the overall performance of ouralgorithms. Algorithms operating in this manner are termed ``online algorithms''.
The book studies an attractive frameworks called competitive analysiswithin which such problems can be analyzed and solved. In this frameworkthe goodness of an algorithm is measured relative to the best possibleperformance of an algorithm that has complete knowledge of the future.The book provides an in-depth presentation of this quite recent approachfor the analysis of online decision making, an approach that become thestandard in theoretical computer science. To this end the book presentsand analyzes various practical and more abstract algorithmic problems suchas paging in a virtual memory system, routing in a communication networkand stock portfolio selection.
Click here to send e-mailabout errata or comments about this page
Otherlinks relevant to online computation and competitive analysis
1998 7 x 10 c. 432 pp. 39 line diagrams 7 tables
Hardback 0-521-56392-5 PST 35.00 $54.95