subject

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 Xi ⊆ {G1, . . . , Gk} 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 Uj ⊆ {G1, . . . , Gk} 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.

Please give the algorithm and the proof and the running time.

ansver
Answers: 3

Other questions on the subject: Computers and Technology

image
Computers and Technology, 23.06.2019 08:00, hernandez09297
What is a scenario where records stored in a computer frequently need to be checked
Answers: 2
image
Computers and Technology, 24.06.2019 00:20, talyku843
Describe a data structures that supports the stack push and pop operations and a third operation findmin, which returns the smallest element in the data structure, all in o(1) worst-case time.
Answers: 2
image
Computers and Technology, 24.06.2019 11:00, iloveballet1857
Each row in a database is a set of unique information called a(n) ? a.) table. b.) record. c.) object. d.) field.
Answers: 2
image
Computers and Technology, 24.06.2019 15:30, jhony70
What type of forensic evidence was recovered during the bomb set off at the new mexico facility on the video that was similar to the evidence obtained at the boston bombings and how did the evidence allow the researchers to connect other pieces of evidence to the same bomb?
Answers: 2
You know the right answer?
Back in the euphoric early days of the Web, people liked to claim that much of the enormous potentia...

Questions in other subjects: