[request_ebook] Online Computation and Competitive Analysis

Description

Information is perhaps the most important ingredient for all computational tasks. It is generally true that the more input information is given, the better algorithmic performance one can expect.

Don't we all have experiences with such scenarios? Have you ever wondered whether to hold onto your IBM stocks or sell them now? Should you pay $700 dollars 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 cache or replace it right away? The common denominator of such problems is the constraint 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 given one piece at a time, and upon receiving an input, the algorithm must take an irreversible action without the knowledge of future inputs. That is, once an action is taken, either we cannot undo it at all or the undoing will incur a cost, which adversely affects the overall performance of our algorithms. Algorithms operating in this manner are termed ``online algorithms''.

The book studies an attractive frameworks called competitive analysis within which such problems can be analyzed and solved. In this framework the goodness of an algorithm is measured relative to the best possible performance of an algorithm that has complete knowledge of the future. The book provides an in-depth presentation of this quite recent approach for the analysis of online decision making, an approach that become the standard in theoretical computer science. To this end the book presents and analyzes various practical and more abstract algorithmic problems such as paging in a virtual memory system, routing in a communication network and stock portfolio selection.