Deep Dive
Online Algorithms
An introduction to online algorithms and competitive analysis: how to measure the price of deciding before you know the future by comparing an online algorithm against the offline optimum through the competitive ratio, with ski rental as the archetypal example.
8 articles
~95 min total
AlgorithmsOnline AlgorithmsCompetitive AnalysisRandomized AlgorithmsSki RentalPaging
Articles in this Series(showing 2 of 8)
AlgorithmsCompetitive AnalysisOnline AlgorithmsSki Rental
1
Deep Dive
Deciding Without the Future: An Introduction to Online Algorithms
An introduction to online algorithms and competitive analysis: how to measure the price of deciding before you know the future by comparing an online algorithm against the offline optimum through the competitive ratio, with ski rental as the archetypal example.
Jul 2, 202611 min read
AlgorithmsOnline AlgorithmsCompetitive Analysis
2
UpcomingDeep Dive
Ski Rental: The Rent-or-Buy Decision
The ski rental problem, the archetype of online rent-or-buy decisions. The break-even rule is (2 - 1/B)-competitive and provably optimal for deterministic algorithms, while randomization brings the ratio down to e/(e-1), a hands-on first tour of competitive ratios and adversary lower bounds.
Jul 16, 202612 min read
AlgorithmsOnline AlgorithmsCompetitive AnalysisSki Rental