6 min read
On this page

Online Algorithms

Overview

Online algorithms must make decisions as input arrives, without knowledge of future requests. Performance is measured by competitive analysis: comparing the online algorithm's cost to the optimal offline solution (the adversary who sees all input).

Competitive Analysis

An online algorithm ALG is c-competitive if for all input sequences sigma:

cost(ALG, sigma) <= c * cost(OPT, sigma) + b

where OPT is the optimal offline algorithm and b is a constant independent of sigma.

  • Strict competitive ratio: b = 0
  • Lower bound arguments: construct adversarial input sequences
  • Randomized competitive ratio: compare against oblivious adversary

Adversary Models

| Adversary | Knows algorithm? | Knows random bits? | Power | |--------------|------------------|--------------------|-------------| | Oblivious | Yes | No | Weakest | | Adaptive-online | Yes | Sees past bits | Medium | | Adaptive-offline | Yes | Sees all bits | Strongest |

Online Paging (Caching)

Problem: Cache of size k, sequence of page requests. On a miss (page not in cache), must evict a page to load the requested one. Minimize total cache misses.

Deterministic Algorithms

  • LRU (Least Recently Used): evict the page used longest ago
  • FIFO (First In First Out): evict the oldest loaded page
  • LFU (Least Frequently Used): evict the least accessed page

Theorem: LRU and FIFO are k-competitive. No deterministic algorithm achieves better than k-competitive ratio.

Proof sketch (lower bound): adversary always requests the page not in cache. OPT with cache size k misses once per k+1 requests (longest-forward-distance). ALG misses every request.

Randomized Paging: Marking Algorithm

  • Divide requests into phases. Mark a page when requested.
  • On a miss, evict a random unmarked page. When all pages are marked, unmark all.
  • O(log k)-competitive against oblivious adversary
  • Fiat-Karp-Rabani-Wigderson: Randomized Marking is H_k-competitive (H_k = ln k + O(1))
  • This is optimal for randomized algorithms

k-Server Problem

Generalization of paging: k servers on a metric space, serve requests (points) by moving a server to the requested point. Minimize total distance moved.

  • Paging is k-server on a uniform metric (all distances equal)
  • k-Server Conjecture: there exists a k-competitive deterministic algorithm for every metric space
  • Work Function Algorithm (WFA): (2k-1)-competitive for all metrics
  • Randomized: O(log^2 k)-competitive [Bubeck et al. 2018]

Ski Rental Problem

Decision: rent skis at cost 1 per day, or buy for cost B. Unknown number of skiing days.

  • Deterministic optimal: buy on day B. Competitive ratio = 2 - 1/B.
  • Randomized optimal: buy on day sampled from specific distribution. Ratio = e/(e-1) ~ 1.58.

This is the prototypical rent-or-buy problem. Generalizes to:

  • TCP acknowledgment
  • Snoopy caching
  • Bahncard problem (partial discounts)

Online Scheduling

List Scheduling (Graham)

  • n jobs arrive online; assign each to the least loaded of m machines
  • (2 - 1/m)-competitive for makespan minimization

Online Load Balancing

  • Jobs with weights arrive; assign irrevocably to machines
  • Greedy (assign to least loaded): O(log m)-competitive for related machines
  • For identical machines: 1.92-competitive via careful tie-breaking

Online Job Scheduling with Deadlines

  • Jobs have release times, deadlines, processing times
  • EDF (Earliest Deadline First): optimal for single machine preemptive case
  • Non-preemptive: no bounded competitive ratio possible in general

Online Bipartite Matching

Problem: vertices on left are known; right vertices arrive online with their edges. Must match irrevocably upon arrival. Maximize matching size.

Deterministic: Greedy

  • Match each arriving vertex to any available neighbor
  • Competitive ratio = 1/2 (tight: path graph)

Randomized: RANKING Algorithm [Karp-Vazirani-Vazirani 1990]

  1. Permute left vertices in random order at the start
  2. Match each arriving right vertex to its available neighbor with highest rank
  • Competitive ratio = 1 - 1/e ~ 0.632
  • Optimal for online bipartite matching against oblivious adversary

AdWords Problem

  • Generalization: bidders have budgets, items arrive, assign to maximize revenue
  • (1 - 1/e)-competitive when bids are small relative to budgets
  • Central to search engine ad auctions

Secretary Problem

Problem: n candidates arrive in random order. After each interview, must irrevocably accept or reject. Hire the single best candidate.

Optimal Strategy

  1. Reject the first n/e candidates (observation phase)
  2. Accept the first subsequent candidate better than all observed so far
  • Probability of selecting the best: 1/e ~ 0.368
  • Optimal among all stopping rules

Variants

  • k-choice secretary: select k candidates, maximize total value
  • Matroid secretary: select an independent set in a matroid
  • Knapsack secretary: items have sizes and values, capacity constraint
  • Matroid secretary conjecture: O(1)-competitive algorithm exists

Prophet Inequalities

Setting: n independent random variables X_1, ..., X_n with known distributions. Observe sequentially, select at most one. Maximize expected selected value.

Classic Result (Krengel-Sucheston)

Set threshold t = median of max(X_1, ..., X_n). Accept the first X_i >= t.

  • E[ALG] >= (1/2) * E[max X_i]
  • Factor 1/2 is tight for deterministic thresholds
  • Improved to 1 - 1/e for IID distributions

Prophet Inequality for Multiple Selection

  • Select k items: (1 - 1/sqrt(k+3))-competitive
  • Matroid constraint: 1/2-competitive via threshold policies

Applications

  • Posted-price mechanisms in auction design
  • Online resource allocation
  • Optimal stopping theory

Multiplicative Weights Update (MWU)

A meta-algorithm for online decision-making under uncertainty.

Framework

  • n experts, T rounds
  • Each round, choose a distribution over experts; observe losses
  • Update: multiply each expert's weight by (1 - epsilon)^loss
Initialize w_i = 1 for all experts i
For t = 1 to T:
    Play distribution p_i = w_i / sum(w_j)
    Observe loss vector l_t (each l_t(i) in [0, 1])
    Update w_i = w_i * (1 - epsilon)^l_t(i)

Regret Bound

Total loss of MWU minus total loss of best expert in hindsight:

Regret <= epsilon * T + (ln n) / epsilon

Setting epsilon = sqrt(ln n / T):

Regret <= 2 * sqrt(T ln n)

This is O(sqrt(T log n)), which is optimal.

Applications

  • Boosting (AdaBoost is a form of MWU)
  • Zero-sum game solving: converges to Nash equilibrium
  • LP solving: approximate LP solutions without simplex/interior point
  • Online convex optimization: generalized to continuous domains
  • Hedge algorithm for portfolio selection

Connections

  • Equivalent to mirror descent with KL divergence
  • Related to follow-the-regularized-leader (FTRL) with entropy regularization
  • Extends to bandit settings (EXP3 algorithm)

Online Convex Optimization (OCO)

Generalization of expert problem to continuous decision spaces.

  • Each round: pick x_t from convex set K, suffer loss f_t(x_t)
  • Online Gradient Descent: x_{t+1} = Project_K(x_t - eta * gradient(f_t(x_t)))
  • Regret O(sqrt(T)) for convex losses, O(log T) for strongly convex losses

Key Results Summary

| Problem | Deterministic | Randomized | |-----------------------|----------------|----------------| | Paging | k | H_k ~ ln k | | Ski Rental | 2 | e/(e-1) ~ 1.58 | | Bipartite Matching | 1/2 | 1 - 1/e | | k-Server (general) | 2k - 1 | O(log^2 k) | | List Scheduling | 2 - 1/m | — |

Summary

Online algorithms address the fundamental challenge of decision-making under uncertainty. Competitive analysis provides worst-case guarantees, while randomization often yields significant improvements. The multiplicative weights framework unifies many online learning problems and connects to optimization, game theory, and machine learning.