Exercise 8.4.1 : Using the simplifying assumptions of Example 8.7, suppose

that there are three advertisers, A, B, and C. There are three queries, x, y, and

z. Each advertiser has a budget of 2. Advertiser A bids only on x; B bids on x

and y, while C bids on x, y, and z. Note that on the query sequence xxyyzz,

the optimum off-line algorithm would yield a revenue of 6, since all queries can

be assigned.

! (a) Show that the greedy algorithm will assign at least 4 of these 6 queries