Let me begin with a disclaimer! Online algorithms, the subject topic of this book, have nothing to do with the internet or the online connected world. Online algorithms should really be called limited information algorithms or myopic algorithms that have to make decisions with limited information while being compared against the best algorithm in hindsight.

The simplest example of an online algorithm is the game of Tetris, where at each time, the player has to make a decision about where to place the newly arrived tile, given the current state of tile positions and the knowledge of only the newly revealed tile and the next upcoming tile, so as to make as many completed lines with similar colour disappear as possible. Clearly, if all the future arriving tiles were revealed at each time, the optimal placement of the newly arrived tile to maximize the number of completed lines can be computed. However, with the limited information setting of the game, the quest is to get as close to the optimal algorithm in hindsight.

To put online algorithms in perspective, let's ask a question: what does an algorithm usually do? Given a (full) input instance, it provides a routine to optimize an objective function, subject to a set of constraints. When the full input instance is known before the algorithm starts to execute, it is referred to as the offline setting.

For many optimization problems of interest, however, the input instance is revealed sequentially, and an algorithm has to execute or make irrevocable decisions sequentially with the partially revealed input amid uncertainty about the future input, e.g., as we discussed for the game of Tetris. This sequential decision setting is generally referred to as the online setting, and the corresponding algorithm as an online algorithm. Compared to the offline algorithm, an online algorithm's output is a function of its sequentially made decisions and the order in which input is revealed.

To contrast the offline versus the online setting, consider one of simplest problems of memory management in random access memory (RAM) of computing systems. RAM is a fast but limited sized memory, and files before processing have to be loaded in the RAM. At each step of computation, a file is requested. If the requested file is available in the RAM, then execution starts immediately. Otherwise, a fault is counted to model the delay, etc., for loading the requested file into the RAM before execution.