Deciding without the future
An online algorithm must make decisions as inputs arrive, never seeing what comes next. Contrast this with an offline optimum that knows the whole sequence in advance. The natural question is how much the lack of foresight costs.
The competitive ratio
The competitive ratio is the worst case ratio between the online algorithm's cost and the best possible offline cost on the same input. A smaller ratio is better, and a ratio of one would mean clairvoyance is no advantage.
- It is measured against an adversary who designs the worst input.
- It bounds performance with no probabilistic assumptions.
A classic example
In the ski rental problem you either pay each day to rent or pay once to buy, not knowing how many days you will ski. Buying right when rentals would have equaled the purchase price guarantees you never pay more than about twice the offline optimum.
Randomization helps
A deterministic online algorithm faces an adversary that sees its rule. A randomized algorithm hides its next move, so the adversary must plan against a distribution, which can lower the achievable competitive ratio below the deterministic limit.
Key idea
The competitive ratio scores an online algorithm by its worst case cost relative to an offline optimum that knows the future, and randomization can beat the deterministic bound by hiding the next move from the adversary.