Back in the euphoric early days of the web, people liked to claim that much of the enormous potential in a company like yahoo! was in the "eyeballs"-the simple fact that millions of people look at its pages every day. further, by convincing people to register personal data with the site, a site like yahoo! can show each user an extremely targeted advertisement whenever he or she visits the site, in a way that tv networks or magazines couldn't hope to match. so if a user has told yahoo! that he or she is a 20-year-old computer science major from cornell university, the site can present a banner ad for apartments in ithaca, new york: on the other hand, if he or she is a 50-year-old investment banker from greenwich, connecticut, the site can display a banner ad pitching lincoln town cars instead. but deciding on which ads to show to which people involves some serious computation behind the scenes. suppose that the managers of a popular web site have identified k distinct demographic groups g1, g2, gk. (these groups can overlap: for example, g1 can be equal to all residents of new york state, and g2 can be equal to all people with a degree in computer science.) the site has contracts with m different advertisers, to show a certain number of copies of their ads to users of the site. here's what the contract with the ith advertiser looks like. for a subset x_i {g_1, g_k} of the demographic groups, advertiser i wants its ads shown only to users who belong to at least one of the demographic groups in the set xi. for a number ri, advertiser i wants its ads shown to at least ri users each minute. now consider the problem of designing a good advertising policy-a way to show a single ad to each user of the site. suppose at a given minute, there are n users visiting the site. because we have registration information on each of these users, we know that user j (for j = 1, 2, n) belongs to a subset u_j (g_j, g_k} of the demographic groups. the problem is: is there a way to show a single ad to each user so that the site's contracts with each of the m advertisers is satisfied for this minute? (that is, for each i = 1, 2,, m, can at least ri of the n users, each belonging to at least one demographic group in xi, be shown an ad provided by advertiser i? ) give an efficient algorithm to decide if this is possible, and if so, to actually choose an ad to show each user.