Online Algorithms, Competitive Analysis & Caching Strategies | Chapter 27 in Introduction to Algorithms

Chapter 27 of Introduction to Algorithms explores the fascinating world of online algorithms—those that operate without access to future input. Unlike offline algorithms, which can optimize decisions with full knowledge of the input sequence, online algorithms must make real-time choices. This chapter introduces competitive analysis as a framework for evaluating their effectiveness and walks through key applications like list maintenance, caching, and scheduling. From the Move-to-Front (MTF) heuristic to randomized caching strategies like RANDOMIZED-MARKING, this chapter offers foundational concepts critical to understanding real-world systems such as memory management and web caching.

Watch the video above for a complete walkthrough of Chapter 27, and read on for a full breakdown of the core models, algorithms, and theorems that define online decision-making in algorithm design.

✅ What Are Online Algorithms?

• Process input piece-by-piece as it arrives
• Cannot revise past decisions once made
• Common applications include job scheduling, route planning, dynamic pricing, and memory caching
• Require conservative design to handle all potential input sequences

✅ Competitive Analysis

• Evaluates an online algorithm A by comparing its performance on input I to an optimal offline algorithm F
• A(I): Cost of the online algorithm
• F(I): Cost of the optimal offline algorithm
• Competitive ratio: max_I A(I)/F(I)
• An algorithm is c-competitive if A(I) ≤ c × F(I) for all I

✅ Example: Waiting for an Elevator

• Choice: wait for elevator (arrival time m) or take stairs (fixed time k)
• Offline optimal: Take elevator if m < k – 1; otherwise, take stairs
• Strategies:
• Always stairs → ratio = k
• Always elevator → ratio = B / k (B = max wait time)
• Hedging (wait k, then stairs) → ratio = 2

✅ Search List Maintenance – Move-to-Front (MTF)

• MTF: After accessing element x at position r, move x to front
• Cost: 2r – 1 (r for search, r – 1 for swaps)
• Compared to: FORESEE, an optimal offline algorithm with full access sequence
• Theorem 27.1: MTF is 4-competitive

✅ Online Caching (Paging Problem)

• Cache can hold k blocks; blocks arrive sequentially
• Cache miss: Must load block and possibly evict one
• Cache hit: No change
• Eviction must be done without future knowledge

🔸 Deterministic Policies

• FIFO: Evict oldest block
• LIFO: Evict most recent block
• LRU: Evict least recently used block
• LFU: Evict least frequently used block

🔸 Competitive Ratios

• LIFO → Θ(n / k), unbounded as n increases
• LFU → Also unbounded
• LRU → O(k)
• FIFO → O(k)
• Theorem 27.4: Every deterministic algorithm has lower bound Ω(k)

✅ Randomized Caching Algorithms

• Can outperform deterministic lower bounds
• Oblivious adversary: Cannot see random choices
• Nonoblivious adversary: Can react to algorithm randomness

🔸 RANDOMIZED-MARKING Algorithm

• Each cache block has a mark bit
• On miss:
• If all blocks are marked → unmark all
• Evict a random unmarked block
• Theorem 27.5: Competitive ratio = O(log k) (against oblivious adversary)

📘 Glossary of Key Terms

• Online Algorithm: Makes decisions incrementally without knowing the future
• Offline Algorithm: Knows full input beforehand
• Competitive Ratio: Measures worst-case performance relative to optimal
• Move-to-Front (MTF): Heuristic to reorder lists based on recent access
• Inversion: Misordered pairs between two sequences
• Cache Miss / Hit: Whether requested data is already in memory
• FIFO / LRU / LFU / LIFO: Cache replacement strategies
• Oblivious Adversary: Cannot adapt to algorithm’s random choices
• MARKING / RANDOMIZED-MARKING: Caching strategy using bits to track usage
• Epoch: A defined time window or cycle for algorithmic resets
• Expected Competitive Ratio: Average-case performance for randomized algorithm

👉 Watch the full episode on YouTube for visuals and worked examples.

📘 Want more summaries from Introduction to Algorithms? Visit the full blog archive.

🔔 Don’t forget to subscribe to Last Minute Lecture for weekly chapter breakdowns, algorithm tutorials, and textbook walkthroughs!