7. Web Advertising

Question 1

How do online algorithms differ from the offline or classic model of algorithms?

Answer 1

In the classic model, you seethe entire input and then compute some function on it.
In the online model, you see the input one piece at a time and need to make irrevocable decisions along the way similar to streams

Question 2

What is a perfect matching in bipartite matching?

Answer 2

When all vertices of the graph are matched

Question 3

What is a maximum matching in bipartite matching?

Answer 3

A matching that contains the largest possible number of matches

Question 4

What is the goal of a matching algorithm?

Answer 4

To find a maximum matching for a given bipartite graph. A perfect one should be found if it exists

Question 5

What is the difference between the online and offline matching algorithms?

Answer 5

The offline algorithm runs in polynomial time and is based on augmenting paths.
The online algorithm is used when we do not know the entire graph up front

Question 6

What is the general flow of the online graph matching problem?

Answer 6

1. Initially we are given all members of one set
2. In each round, one member of the other set has their edges revealed
3. At that time we either decide to pair the new member with one from the first set or do not pair it with any thing from the other set

Question 7

How does the greedy algorithm solve the online matching problem?

Answer 7

Pairs the new element from set 2 with any eligible item from set 1. If there is none, do not pair the item

Question 8

What is the competitive ratio?

Answer 8

A way to measure the worst performance of the greedy algorithm over all possible inputs

Ratio = min (|Mgreedy| / |Mopt|) for all possible inputs I

Question 9

What is the value of the competitive ratio when Mgreedy != Mopt?

Answer 9

|Mgreedy|/|Mopt| >= 1/2

Question 10

What is performance-based advertising?

Answer 10

Where advertisers bid on search keywords so the highest bidder’s ad is shown on that word. The advertiser is only charged if the ad is clicked on

Question 11

What is the adwords problem?

Answer 11

A search engine needs to determine a subset of advertisers whose ads will e shown for a query with the goal of maximizing revenue for the search engine

Question 12

What is the simple solution to the adwords problem?

Answer 12

Instead of using raw bids, calculate expected revenue per click using the product of the bid and the click-through rate of the ad

Question 13

What are the two complications of the adwords problem?

Answer 13

1. Click-through rate of an ad is unknown
2. Advertisers have a limited budget and the search engine guarantees the advertiser won’t be charged more than their daily budget

Question 14

What information are we given in the adwords problem?

Answer 14

1. A set of bids by advertisers for search queries
2. A click-through rate for each advertiser-query pair
3. A budget for each advertiser
4. A limit on the number of ads to be displayed with each query

Question 15

What is the goal of the adwords problem?

Answer 15

To respond to each query with a set of advertisers such that:
1. The size of the set is no larger than the number of ads limit
2. Each advertiser has bid on the query
3. Each advertiser has enough budget left to pay for the ad if it is clicked on

Question 16

What is the exploration vs exploitation problem?

Answer 16

Trying to decide if we should keep showing an ad for which we have good estimate of click-through rate (exploit) or should we show a brand new ad to get a better sense of click-through rate (explore)

Question 17

What are the parameters for the simplified environment in the adwords problem?

Answer 17

1. There is 1 ad shown for each query
2. All advertisers have the same budget
3. All ads are equally likely to be clicked
4. Value of each ad is the same

Question 18

What is the BALANCE algorithm?

Answer 18

A solution to the adwords problem that picks the advertiser with the largest unspent budget for each query. It breaks ties arbitrarily but deterministically unlike the greedy approach which breaks ties the same way every time

Question 19

What is the worst competitive ratio of BALANCE?

Answer 19

In the general case, 1-1/e = 0.63 approx