Online Algorithms & Competitive Analysis | Chapter 27 – Introduction to Algorithms (4th) скачать в хорошем качестве

Online Algorithms & Competitive Analysis | Chapter 27 – Introduction to Algorithms (4th)

Chapter 27 introduces online algorithms, which must make decisions without knowledge of future input. These contrast with offline algorithms, which have the full input sequence available from the start. The chapter introduces competitive analysis as a framework for evaluating online algorithms by comparing their worst-case performance to an optimal offline algorithm. Key applications include search list maintenance, caching, and scheduling. ✅ What Are Online Algorithms? 🔸 Process input piece-by-piece as it arrives 🔸 Cannot revise past decisions 🔸 Examples: memory caching, job scheduling, dynamic pricing, and route planning 🔸 Online algorithms must be designed conservatively to handle all inputs ✅ Competitive Analysis 🔸 Compares online algorithm A to optimal offline algorithm F 🔸 For input I:  🔸 A(I) is the cost of the online algorithm  🔸 F(I) is the cost of the optimal offline algorithm 🔸 Competitive ratio: max over all I of A(I) / F(I) 🔸 Goal: minimize worst-case ratio 🔸 An algorithm is c-competitive if A(I) ≤ c × F(I) for all inputs ✅ Example: Waiting for an Elevator 🔸 Decide whether to wait for elevator (arrival time m) or take stairs (fixed time k) 🔸 Offline optimal: take elevator if m (less than) k – 1; otherwise take stairs 🔸 Strategies:  🔸 Always take stairs → competitive ratio = k  🔸 Always take elevator → ratio = B / k (B = max wait)  🔸 Hedging: wait k minutes, then take stairs → competitive ratio = 2 ✅ Search List Maintenance – Move-to-Front (MTF) 🔸 Online list-update algorithm 🔸 After accessing element x (at position r), move it to the front 🔸 Cost = 2r – 1 (r to find, r – 1 swaps) 🔸 Compared to FORESEE, an optimal offline algorithm that knows the full access sequence 🔸 Inversion count measures difference between online and offline order 🔸 Theorem 27.1: MTF is 4-competitive ✅ Online Caching (Paging Problem) 🔸 Memory blocks arrive sequentially; cache can hold k blocks 🔸 On a cache miss, must bring in block and possibly evict another 🔸 On a cache hit, no changes occur 🔸 Online algorithms decide eviction policy without knowing future requests 🔸 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, grows with n  🔸 LFU → also unbounded  🔸 LRU → O(k)  🔸 FIFO → O(k) 🔸 Theorem 27.4: Any deterministic caching algorithm has a lower bound of Ω(k) ✅ Randomized Caching Algorithms 🔸 Can beat deterministic lower bounds using randomness 🔸 Adversaries:  🔸 Oblivious: unaware of algorithm's random choices  🔸 Nonoblivious: can react to random outcomes (more powerful) 🔸 RANDOMIZED-MARKING Algorithm  🔸 Each block has a mark bit  🔸 On cache miss:   🔸 If all blocks are marked → unmark all   🔸 Evict one unmarked block uniformly at random  🔸 Theorem 27.5: Expected competitive ratio = O(log k) (against oblivious adversary) 📘 Read full blog summaries for every chapter: https://lastminutelecture.com 📘 Have a book recommendation? Submit your suggestion here: https://forms.gle/y7vQQ6WHoNgKeJmh8 Thank you for being a part of our little Last Minute Lecture family! ⚠️ Disclaimer: These summaries are created for educational and entertainment purposes only. They provide transformative commentary and paraphrased overviews to help students understand key ideas from the referenced textbooks. Last Minute Lecture is not affiliated with, sponsored by, or endorsed by any textbook publisher or author. All textbook titles, names, and cover images—when shown—are used under nominative fair use solely for identification of the work being discussed. Some portions of the writing and narration are generated with AI-assisted tools to enhance accessibility and consistency. While every effort has been made to ensure accuracy, these materials are intended to supplement—not replace—official course readings, lectures, or professional study resources. Always refer to the original textbook and instructor guidance for complete and authoritative information.