Advertisements have become a major medium of revenue for the Web. It is a billion dollar business and is the source for revenue of most leading companies in Silicon Valley. Further, it has made it possible for companies such as Google, Facebook, Yahoo!, and Twitter to run their main services for free while collecting their revenue through advertisements.

Adwords lets people bid for keywords. For example, advertiser A can bid for the keyword, Hadoop Support, for $2 and provide a maximum budget of $100. Advertiser B can bid for the keyword, Hadoop Support, for $1.50 and provide a maximum budget of $200. When a user searches for a document with the given keywords, the system will choose one or more advertisements among the bids for these keywords. Advertisers will pay only if a user clicks on the advertisement.

The goal is to select advertisements such that they will maximize revenue. There are several factors in play when...