Online Algorithms

Algorithms that must make irrevocable decisions without knowing the complete input in advance. Unlike traditional algorithms that have full access to their input, online algorithms see input piece-by-piece and must commit to decisions immediately. Performance is measured via competitive analysis—comparing the algorithm’s cost to the optimal offline algorithm that knows the entire input sequence.

Intermediate to Advanced

• Basic concepts (ski rental, paging): Intermediate
• Competitive analysis: Intermediate to Advanced
• Primal-dual online algorithms: Advanced
• Secretary problem and optimal stopping: Intermediate
• Advanced applications (online matching, learning): Advanced

Real-time decision-making is everywhere: The modern world demands algorithms that make decisions in real-time without complete information:

• Network routers must forward packets without knowing future traffic
• Cloud providers must allocate resources without knowing what jobs arrive next
• Trading algorithms must decide now whether to buy/sell
• Caching systems must decide what to evict without knowing future accesses

War Story - The Ski Rental Problem: You’re going on vacation to a ski resort. Renting skis costs $50/day. Buying costs $500. You don’t know how many days you’ll ski. What do you do?

This seemingly trivial question captures the essence of online algorithms: making decisions under uncertainty. The optimal strategy: rent for exactly 10 days, then buy on day 11 if you’re still skiing. This 2-competitive strategy guarantees you never pay more than twice the optimal cost (in hindsight).

This pattern appears everywhere:

• Lease vs. buy equipment
• Pay-as-you-go vs. subscription services
• Reserve vs. on-demand cloud computing
• Temporary vs. permanent hires

War Story - The Secretary Problem: You’re interviewing candidates sequentially. After each interview, you must immediately accept or reject—no callbacks. How do you maximize your chance of hiring the best candidate?

This classic problem reveals deep insights about optimal stopping. The solution: interview 37% (≈ n/e) of candidates as a “calibration phase,” then hire the first person better than all previous ones. You’ll hire the best with 37% probability—provably optimal!

This strategy applies to apartment hunting, choosing life partners (per Algorithms to Live By), or any sequential decision where you can’t go back.

1. Ski Rental - Fundamental rent-vs-buy analysis
2. Paging (LRU, FIFO, LFU) - Cache replacement strategies
3. List Update (Move-to-Front) - Self-organizing data structures
4. Secretary Problem - Optimal stopping theory
5. Online Bipartite Matching - Greedy matching with competitive ratio

6. k-Server Problem - Generalization of paging to metric spaces
7. Metrical Task Systems - General framework for online problems
8. Primal-Dual Online Algorithms - LP-based competitive algorithms
9. Multiplicative Weights Update - Online learning framework
10. Online Convex Optimization - Online gradient descent and variants
11. Prophet Inequalities - Online selection with known distributions

• Required:

  • Basic algorithms (greedy, divide-and-conquer)
  • Big-O notation and asymptotic analysis
  • Basic probability (for randomized online algorithms)

• Helpful:

  • Linear programming (for primal-dual algorithms)
  • Probability theory (for prophet inequalities, online learning)
  • Game theory intuition (adversarial analysis)

Setup: Your computer has fast memory (cache) that holds 4 pages, but needs to access a sequence of pages from slow memory (disk). When requesting a page not in cache, you must evict something. You don’t know future requests. What do you evict?

Naive approaches:

• FIFO (First-In-First-Out): Evict oldest page
• LIFO (Last-In-First-Out): Evict newest page
• Random: Evict random page

Clever approach - LRU (Least Recently Used): Evict the page not used for the longest time. Intuition: the past predicts the future.

Analysis reveals: LRU is k-competitive for cache size k. No deterministic algorithm can do better! This is optimal among deterministic algorithms.

The insight: We can’t beat the adversary by much, but we can characterize exactly how close we can get. Competitive analysis makes this precise.

Real-world impact: Every operating system uses variants of LRU for page replacement. Understanding the competitive ratio explains why.

Setup: You’re driving down a street looking for parking. Spots appear at random distances from your destination. Each spot passed costs you time. Walk-back distance also costs time. When do you park?

Naive approach: Park in the first available spot. But you might waste walking time.

Greedy approach: Only park if the spot is closer than expected remaining spots. But this requires knowing the distribution!

Online challenge: You don’t know how many spots remain or where they are. You must decide immediately whether to take each spot.

Solution: With uniform spot distribution, optimal strategy: park if spot is within distance d* from destination (computable from distribution). This gives provable competitive ratio.

Generalization: This models broader resource allocation decisions—accept job offer now or wait for better? Take apartment or keep searching? Buy stock now or wait for lower price?

Setup: Advertisers bid for keywords (e.g., “running shoes”). When users search, Google must immediately assign ads to slots without knowing future queries. Each advertiser has a budget. How do you maximize revenue?

Naive approach: Greedy—assign to highest bidder. But this might exhaust budgets early, leaving revenue on the table.

Online challenge: Queries arrive sequentially. Assignment must be immediate. Future queries unknown.

Breakthrough - Greedy with Balance: Balance remaining budgets when allocating. The algorithm achieves (1 - 1/e) ≈ 0.63 competitive ratio when budgets are large—provably optimal!

Real-world impact: Variants of this algorithm power Google AdWords, generating over $200 billion annually. The competitive analysis provides theoretical guarantees for a system affecting the entire internet economy.

The explore-exploit tradeoff: Multi-armed bandits model choosing between known options (exploit) vs. trying new ones (explore):

• Which restaurant to try?
• Which route to take?
• Which strategy to invest in?

The optimal solution balances exploration early with exploitation later. This formalizes the intuition that young people should experiment while older people should leverage experience.

Optimal stopping in daily life: The 37% rule from the secretary problem provides concrete advice:

• Apartment hunting: Look at 37% of available apartments, then take the first one better than all previous
• Hiring: Interview 37% of timeline, then make offer to first better candidate
• Relationship advice: Date 37% of “dating years,” then commit to next person better than all previous (per Algorithms to Live By)

The rule feels counterintuitive but is provably optimal for these sequential decision problems.

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

ALG(σ) ≤ c · OPT(σ) + α

where OPT(σ) is the optimal offline cost and α is a constant.

Interpretation: The online algorithm performs at most c times worse than omniscient optimal, plus some additive constant.

1. Oblivious adversary: Generates entire input sequence in advance (doesn’t see algorithm’s random choices)
2. Adaptive adversary: Sees algorithm’s decisions and random choices, adapts future input
3. Fair adversary: Sees past decisions but not current random choice

Why this matters: Stronger adversaries ⟹ harder analysis but more realistic guarantees.

Deterministic paging: k-competitive (tight) Randomized paging against oblivious adversary: O(log k)-competitive (exponentially better!)

The insight: Randomization defeats adversarial patterns. If the adversary doesn’t know your random choices, they can’t exploit worst cases.

Define potential Φ(state) such that:

• amortized cost = actual cost + Δ Φ
• Show amortized cost ≤ c · OPT’s cost

Used extensively for proving competitive ratios.

Maintain primal and dual LP solutions:

• Algorithm decisions correspond to increasing dual variables
• Competitive ratio follows from LP weak duality

Powerful framework unifying many online algorithms.

Maintain weights on experts/choices:

• Update: w_i ← w_i · (1 - ε)^(loss_i)
• Choose based on weights
• Achieves logarithmic regret bounds

Connects online algorithms to learning theory.

• Borodin & El-Yaniv “Online Computation and Competitive Analysis” - The definitive reference
• Kleinberg & Tardos §13.14 - Excellent introduction to online algorithms
• Algorithmic Game Theory Ch. 6 - Covers online auctions and mechanisms
• Christian & Griffiths “Algorithms to Live By” - Popular science treatment with real-life applications

• Brown CSCI 2950-w - Claire Mathieu’s course (excellent notes)
• Princeton COS 521 - Includes competitive analysis throughout
• CMU 15-750 - Multiplicative weights extensive coverage
• Allan Borodin’s course notes - University of Toronto

• Sleator & Tarjan “Amortized Efficiency of List Update and Paging Rules” (1985) - Classic paging analysis
• Karp, Vazirani & Vazirani “Online Bipartite Matching” (1990) - Breakthrough result
• Mehta et al. “AdWords and Generalized Online Matching” (2007) - Google’s ad allocation

• Approximation Algorithms: Competitive analysis similar to approximation ratios
• Game Theory: Adversarial model connects to minimax strategies
• Machine Learning: Online convex optimization is foundation of online learning
• Randomized Algorithms: Randomization often improves competitive ratios exponentially
• Primal-Dual Methods: LP duality provides powerful analysis framework
• Caching/Systems: Direct applications to OS design, databases
• Economics: Mechanism design, auctions, secretary problem variants

1. Cache Simulator & Comparator

   • Implement multiple caching strategies (LRU, LFU, FIFO, Random, optimal offline)
   • Test on real memory access traces
   • Visualize performance and competitive ratios
   • Measure gap between online and offline optimal

2. Secretary Problem Variants

   • Interactive secretary problem game
   • Test different strategies (37% rule, variants)
   • Extend to multiple positions, known distributions
   • Apply to real-world scenarios (apartment hunting simulator)

3. Online Matching System

   • Implement online bipartite matching algorithms
   • Simulate ride-sharing driver-passenger matching
   • Compare greedy vs. balanced algorithms
   • Measure competitive ratios empirically

4. Ad Auction Simulator

   • Build simplified ad auction system
   • Implement balance-based allocation
   • Simulate advertiser bidding and budget constraints
   • Visualize revenue and competitive performance

5. Multiplicative Weights Framework

   • Implement expert learning with MWU
   • Apply to online routing, portfolio selection
   • Visualize regret bounds over time
   • Compare to other online learning methods

6. Ski Rental Generalization

   • Solve generalized rent-vs-buy problems
   • Apply to cloud computing (reserve vs. on-demand)
   • Equipment lease-vs-purchase analysis
   • Find optimal switching points

2-3 lectures depending on depth

• 2 lectures: Core concepts (ski rental, paging, secretary problem), competitive analysis basics
• 3 lectures: + k-server, primal-dual methods, multiplicative weights
• 4 lectures: + Online learning, prophet inequalities, advanced applications

1. “Online algorithms are just greedy algorithms”

   • False! While many online algorithms are greedy, the competitive analysis framework is distinct. Not all greedy algorithms have good competitive ratios, and not all competitive algorithms are greedy.

2. “Competitive ratio measures average-case performance”

   • False! It’s worst-case over all inputs. The adversarial model is pessimistic but provides guarantees.

3. “Lower competitive ratio is always better”

   • True for comparison, but a 10-competitive algorithm might outperform a 2-competitive one in practice if the worst case is rare.

4. “Online algorithms can’t use past information”

   • False! They can use all past information, just not future information. LRU explicitly uses access history.

5. “Randomization always helps”

   • False! Some problems have the same competitive ratio deterministically and randomly. Randomization helps when it prevents adversarial exploitation.

6. “Online algorithms are a niche topic”

   • False! Most real-world systems are inherently online—packet routing, scheduling, resource allocation, caching, trading. It’s everywhere.

Traditional (banking model):

“Here’s the definition of competitive analysis. Here’s the formula for competitive ratio. Memorize LRU. Now prove this bound.”

Problem-posing approach:

“Your computer needs to decide what to evict from cache right now. You don’t know what pages you’ll need next. What would you do? Try FIFO… now try LRU… which feels better? Let’s formalize this intuition. How can we measure ‘how much worse’ we are than someone who could see the future? Let’s define competitive ratio…”

The difference: Students discover the need for competitive analysis through confronting the challenge of decision-making under uncertainty. The framework emerges as a solution to the problem of evaluating algorithms without complete information.

Curriculum placement:

• Week 6-8 for graduate courses (after greedy, possibly with or after randomized algorithms)
• Can integrate throughout (paging with caching systems, secretary with optimal stopping)

Prerequisites check: Students need solid algorithm analysis skills. Probability background helpful for randomized algorithms. LP knowledge useful but can be introduced as needed.

Why mid-to-late course: Builds on foundational techniques while introducing new evaluation framework (competitive analysis). Natural bridge to applied topics (systems, machine learning).

Machine Learning Connections: Online convex optimization unifies online algorithms and learning theory. Algorithms like online gradient descent achieve regret bounds—the online learning analog of competitive ratios. This connects to:

• Stochastic optimization
• Reinforcement learning
• Bandit algorithms

Beyond Competitive Analysis: Researchers increasingly study:

• Resource augmentation: What if online algorithm has slightly more resources?
• Advice models: What if online algorithm gets hints about the future?
• Learning-augmented algorithms: Combining ML predictions with worst-case guarantees

Applications in AI/ML Systems: Modern ML systems face online challenges:

• Online A/B testing and experimentation
• Real-time recommendation systems
• Dynamic pricing and auctions
• Neural architecture search

Ethical Implications: Online algorithms making irrevocable decisions appear in:

• Hiring (resume screening systems)
• Lending (credit decisions)
• Criminal justice (bail decisions)

Understanding online algorithms helps reason about fairness and accountability in these high-stakes applications.

Ready for students? ✓ Yes - bridges theory and practice, strong real-world motivation, clear connection to everyday decision-making, rigorous mathematical framework with intuitive applications.