This text is an important contribution to the field of online algorithms. In a traditional (offline) algorithm all of the data is present before the algorithm executes. While for an online algorithm the data is presented in a piecewise fashion, most of the data is unknown to the algorithm when it starts executing.

Online algorithms are commonly assessed by the notion of competitive analysis, which compares performance (whether worst-case, average, or best-case) to that of the optimal (theoretical) offline algorithm. This book furthers this exploration by differentiating between deterministic (offline) and randomized (online) with or without advice. Advice is bundled as a certain number of auxiliary bits that contain useful information that an algorithm can use to improve its performance.

The first three chapters of the book deal with the classic paging problem. When one considers the essence of code execution, it is the central processing unit (CPU) and its associated memory that is most critical to that process. Paging concentrates on this memory aspect. Categorically, memory can be of three types: primary, that which the CPU interacts with; secondary, such as a hard drive fixed in the computer; and tertiary, such as a removable universal serial bus (USB) drive. We colloquially refer to the primary memory as random access memory (RAM) because any byte can be addressed directly by referencing its location. However, due to the ever-increasing speeds of CPUs, the primary memory is actually cache. Cache is a very expensive, not plentiful, but extremely fast memory. Lower level memory such as RAM is less expensive and more abundant, but much slower in comparison. The paging problem is to determine at every moment of time which data should remain in cache because that information is in greatest demand by the CPU for processing purposes.

Chapter 1 introduces the paging problem with a deterministic solution. The worst-case scenario is provided by an adversary who at every step of the algorithm constructs the worst possible inputs for the algorithm. In Section 1.5, a general class of marking algorithms is presented for the paging problem. Marking algorithms traverse a directed graph and mark the nodes as needed. Chapter 2 presents the paging problem randomly and also presents the ski rental problem, deciding whether to pay daily a certain cost versus one cost for the entire period. The issue is that you are not certain how long you will need the equipment. Chapter 3 presents the paging problem assuming a certain length of advice (as a measure of complexity) is permitted.

In Section 2.3, Yao’s principle is presented for the finite, infinite, and unbounded cases. This well-quoted principle states that the maximum expected cost (that is, resources necessary) of a randomized algorithm to handle the worst-case set of data cannot be less than the cost of a deterministic algorithm best suited to handle a worst-case random probability distribution presented to it. At the end of these (and all) chapters, the author presents historical and bibliographic references to other approaches and problems dealt with in the literature. As such, the author is trying to present a cohesive approach throughout the entire book, but not an exhaustive one. In addition, exercises are included throughout the book with solutions provided afterwards.

The next chapters discuss five major applications for online algorithms. The k-server problem (chapter 4) determines the best position for servers to be (it is assumed that the servers will actually move to the required position) in order to access information on them faster. The historic job shop scheduling problem (chapter 5) determines the best order to perform tasks so that all deadlines are met and thereby the most profit for accomplishing these tasks can be obtained. Chapter 6 discusses the famous knapsack problem, which is a packing problem: what are the most items one can put into a suitcase (“knapsack”) so that the maximum weight requirement is not violated? The online version is discussed. The very general bit guessing problem is analyzed in chapter 7. Here, a bit must be guessed at every step of an algorithm. The book concludes (chapter 8) with online graph algorithms such as for graph coloring or minimum spanning tree, where a vertex and connecting edges are provided one at a time.

Without a doubt, this text is a must-read for anyone seriously pursuing the analysis of algorithms, particularly online versions of those algorithms.