The canonical first example in online algorithms, "simple enough to demonstrate what's going on" (7:23).

Setup

  • You are at a ski resort with friends; the only unknown is m, the length of the sequence (how many days the vacation lasts) (7:23).
  • Every morning your friends either end the trip or ski one more day; if they ski, you must have skis (7:59).
  • Each day you must either rent for $1 or buy for $B; once bought, all future days are free (8:28).

What OPT does

  • OPT knows the day the friends will go home, so (9:05, 9:25):
    • if #days > B → buy on day 1
    • else → rent every day

The online strategy and its analysis

  • Strategy: rent for B days, buy on day B+1 (if such a day arrives) (9:25).
CaseOPT paysWe pay
#days ≤ B#days#days (10:17)
#days > BBat most 2B (10:30)
  • Result: the strategy is 2-competitive — never more than twice OPT's spend (10:30).
  • Renting for B−1 days and buying on day B does slightly better than 2B, but for large B the ratio still tends to 2 (10:52).