Online Algorithms
An online algorithm processes input sequentially and must make irrevocable decisions about each piece of input before seeing future elements. This contrast...
The Online Setting: Decisions Without Future Knowledge
An online algorithm processes input sequentially and must make irrevocable decisions about each piece of input before seeing future elements. This contrasts with offline algorithms, which have access to the entire input before making any decisions. Online algorithms model real-world scenarios like web caching, job scheduling, network routing, and stock trading, where future requests or prices are unknown at decision time.
The performance of an online algorithm is measured by its competitive ratio, defined as the worst-case ratio of the online algorithm's cost to the optimal offline cost over all possible input sequences. An algorithm is c-competitive if its cost never exceeds c times the optimal offline cost on any input. A deterministic 1-competitive algorithm would be optimal — always achieving the offline optimum — but this is impossible for most non-trivial problems, so the competitive ratio quantifies how much the algorithm suffers for lacking future information.
The ski rental problem is the simplest illustration of the online/offline tradeoff. You are skiing and must decide each day whether to rent skis (cost 1) or buy them (cost B). The optimal offline solution would buy if you ski for B or more days and rent otherwise. The optimal deterministic online algorithm rents for B-1 days and buys on the B-th day if you ski that long, achieving competitive ratio 2 - 1/B (roughly 2). The optimal randomized online algorithm achieves a competitive ratio of e/(e-1) ≈ 1.58 using a random threshold. This simple problem captures the fundamental tension between commitment and regret in online decision-making.
Paging, Caching, and the k-Server Problem
The paging problem models a cache of size k pages in fast memory, with requests arriving online for pages from a large slow-memory pool. On a cache miss, some page must be evicted to make room. The goal is to minimize the total number of cache misses. The optimal offline algorithm is the furthest-in-future (Belady's) algorithm, which always evicts the page whose next request is furthest in the future.
Deterministic online paging algorithms cannot achieve a competitive ratio better than k, and several simple algorithms match this bound. Least Recently Used (LRU) and FIFO are both k-competitive. FIFO evicts the page that has been in cache the longest, while LRU evicts the page that was last accessed longest ago. LRU tends to perform better in practice because access patterns often exhibit temporal locality, but both have the same worst-case guarantee.
The k-server problem generalizes paging to k servers on a metric space, where each request specifies a point and some server must move to serve it. The cost is the total distance traveled by all servers. The k-server conjecture states that the optimal competitive ratio for any metric space is exactly k, and this has been proven for many special cases including the line, trees, and uniform metrics. For general metric spaces, a randomized O(log n log k)-competitive algorithm was found in 2017 by Bubeck et al., resolving a decades-old open problem. Understanding the k-server problem provides a deep appreciation for how geometry and combinatorics interact in online settings.
Streaming Algorithms and Count-Min Sketch
Streaming algorithms are a natural extension of online algorithms where the input is a massive stream that cannot be stored entirely in memory. The goal is to compute aggregate statistics or answer queries about the stream using only polylogarithmic space and constant time per element. Classic streaming problems include estimating the number of distinct elements, finding frequent items, and computing quantiles.
The Count-Min Sketch is a probabilistic data structure for estimating item frequencies in a stream. It uses d hash functions mapping items to positions in w-wide arrays, maintaining d arrays of counters. To update item x, increment the counter at position hash_i(x) in each of the d arrays. To query the frequency of x, return the minimum counter value across all d arrays. The minimum is taken because hash collisions can only inflate counters, never deflate them. With d = ceil(ln(1/delta)) and w = ceil(e/epsilon), the estimated frequency is within epsilon * n of the true frequency with probability at least 1 - delta, where n is the total number of stream elements.
The Flajolet-Martin algorithm estimates the number of distinct elements in a stream (cardinality estimation) using only O(log n) bits. It applies a hash function to each element and tracks the maximum number of trailing zeros in any hash value. If the maximum observed trailing zeros is r, the estimate is 2^r. The HyperLogLog algorithm, a refined version, achieves 1.04/sqrt(m) relative error using m registers, and it powers the COUNT(DISTINCT) operation in many production databases including Redis and PostgreSQL's approximate counting extension.