Questions: Online Algorithms and Competitive Analysis

Question 1

In the ski rental problem, skis cost $B to buy and $1/day to rent. What is the optimal deterministic strategy and its competitive ratio?

• A. Rent for B-1 days, then buy on day B; competitive ratio 2 - 1/B
• B. Buy immediately on day 1; competitive ratio B
• C. Rent forever; competitive ratio is unbounded
• D. Alternate between renting and buying; competitive ratio sqrt(B)

Answer: (A)

If the ski season lasts fewer than B days, renting is optimal (cost < B) and the algorithm rents the whole time (cost < B), so the ratio is at most 1. If the season lasts B or more days, the algorithm rents for B-1 days (cost B-1) then buys (cost B), total 2B-1, while the optimal strategy buys on day 1 (cost B). The ratio is (2B-1)/B = 2 - 1/B. No deterministic strategy can do better: any strategy that buys on day t can be forced to pay t-1 + B by an adversary who ends the season on day t, while the optimum pays min(t, B).

Question 2

For the paging problem with cache size k, no deterministic online algorithm can achieve a competitive ratio better than k.

• T. True
• F. False

Answer: True

An adversary can always request the page that is NOT in the cache, forcing every request to be a fault for the online algorithm. Among any k+1 pages, the adversary requests whichever the algorithm evicts. Over n requests to k+1 pages, the online algorithm faults every time (n faults), while an optimal offline algorithm (Bélády's MIN, which evicts the page used farthest in the future) faults at most n/k times. The competitive ratio is n/(n/k) = k. LRU and FIFO achieve this ratio, making them optimal among deterministic policies. This lower bound uses an adversarial argument specific to deterministic algorithms — randomization breaks it.

Question 3

Randomized online algorithms can achieve strictly better competitive ratios than deterministic ones against an oblivious adversary. Explain why, using the paging problem as an example.

Model answer: Against an oblivious adversary (who must fix the entire request sequence before the algorithm's random choices), the adversary cannot adaptively target the algorithm's eviction decisions. In paging, the randomized marking algorithm achieves competitive ratio O(log k), exponentially better than the deterministic lower bound of k. The algorithm works in phases: it marks pages as they are requested, and when a fault occurs on an unmarked page, it evicts a uniformly random UNMARKED page. The adversary, who commits to the request sequence in advance, cannot know which unmarked page will be evicted, so cannot consistently force faults. This randomization breaks the adversarial construction that proves the deterministic lower bound.

The distinction between adversary types matters: against an adaptive adversary (who sees the algorithm's random bits), randomization provides no benefit and the deterministic lower bound applies. The O(log k) randomized bound versus the Theta(k) deterministic bound for paging is one of the most dramatic separations between deterministic and randomized online algorithms.

Question 4

The competitive ratio of an online algorithm can be improved by allowing the algorithm to see a constant number of future requests (lookahead).

• T. True
• F. False

Answer: True

Even a small lookahead of L future requests can significantly improve competitive ratios. For paging, lookahead L = k (seeing the next k requests) allows the algorithm to simulate Bélády's MIN over a local window, improving the competitive ratio. For some problems like the online matching problem, O(1) lookahead already provides a strict improvement. However, the improvement is problem-specific — some problems have competitive ratio lower bounds that hold even with polynomial lookahead. The relationship between lookahead, advice complexity, and competitive ratio is an active research area.