Advertising on the Web - Mining of Massive Datasets - page 273

8.2.4 Exercises for Section 8.2

! EXERCISE 8.2.1 A popular example of the design of an on-line algorithm to minimize the
competitive ratio is the ski-buying problem . 3 Suppose you can buy skis for $100, or you
can rent skis for $10 per day. You decide to take up skiing, but you don't know if you will
like it. You may try skiing for any number of days and then give it up. The merit of an al-
gorithm is the cost per day of skis, and we must try to minimize this cost.
One on-line algorithm for making the rent/buy decision is “buy skis immediately.” If you
try skiing once, fall down and give it up, then this on-line algorithm costs you $100 per
day, while the optimum off-line algorithm would have you rent skis for $10 for the one
day you used them. Thus, the competitive ratio of the algorithm “buy skis immediately” is
at most 1/10th, and that is in fact the exact competitive ratio, since using the skis one day
is the worst possible outcome for this algorithm. On the other hand, the on-line algorithm
“always rent skis” has an arbitrarily small competitive ratio. If you turn out to really like
skiing and go regularly, then after n days, you will have paid $10 n or $10/day, while the
optimum off-line algorithm would have bought skis at once, and paid only $100, or $100 /n
per day.
Your question: design an on-line algorithm for the ski-buying problem that has the best
possible competitive ratio. What is that competitive ratio? Hint : Since you could, at any
time, have a fall and decide to give up skiing, the only thing the on-line algorithm can use
in making its decision is how many times previously you have gone skiing.

8.3 The Matching Problem
We shall now take up a problem that is a simplified version of the problem of matching
ads to search queries. This problem, called “maximal matching,” is an abstract problem in-
volving bipartite graphs (graphs with two sets of nodes - left and right - with all edges
connecting a node in the left set to a node in the right set. Figure 8.1 is an example of a
bipartite graph. Nodes 1, 2, 3, and 4 form the left set, while nodes a , b , c , and d form the
right set.