Reference no: EM131221452
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.
(b) Find another sequence of queries such that the greedy algorithm can assign as few as half the queries that the optimum off-line algorithm assigns on that sequence.
Example 8.7
Suppose there are two advertisers A and B, and only two possible queries, x and y. Advertiser A bids only on x, while B bids on both x and y. The budget for each advertiser is 2. Notice the similarity to the situation in Example 8.1; the only differences are the fact that the bids by each advertiser are the same and the budgets are smaller here.
Example 8.1
Let us take a very simple example of why knowing the future could help. A manufacturer A of replica antique furniture has bid 10 cents on the search term "chesterfield".2 A more conventional manufacturer B has bid 20 cents on both the terms "chesterfield" and "sofa." Both have monthly budgets of $100, and there are no other bidders on either of these terms. It is the beginning of the month, and a search query "chesterfield" has just arrived. We are allowed to display only one ad with the query.
|
Evaluate the effectiveness of organizations implementation
: For each management system element, discuss the objective evidence you found. Evaluate the effectiveness of the organization's implementation of each element against available reference sources and best practice information.
|
|
File joint income tax return
: Troy and Tracy are married and file a joint income tax return. Their adjusted gross income is $30,000 per year. On last years return, the Tanks claimed a $960 credit for child care expenses. The Tanks are in the 15% marginal income tax bracket. What ..
|
|
Discuss how papa principles of ethics can be applied
: Compare and contrast traditional outsourcing with the Software as a Service (SaaS). Under what conditions should a company choose SaaS over traditional outsourcing? Discuss how PAPA principles of ethics (Motiwalla & Thompson 2012, p.278) can be app..
|
|
How to implement virtual functions in c
: How to Implement virtual functions in C? What is the advantage of new Lock interface over synchronized block in Java? You need to implement a high performance cache which allows multiple reader but single writer to keep the integrity how will you ..
|
|
Find another sequence of queries
: Find another sequence of queries such that the greedy algorithm can assign as few as half the queries that the optimum off-line algorithm assigns on that sequence.
|
|
Preferences of repeat customers
: Angus McIndoe wants to modernize his popular restaurant by adapting it more closely to the preferences of his repeat customers. Keeping track of his customers' likes and dislikes. Information such as where they like to sit, what they like to eat, ..
|
|
What was the annual increase in selling price
: Assume that in January 2013, the average house price in a particular area was $287,400. In January 2001, the average price was $204,300. What was the annual increase in selling price?
|
|
Write the equations for the two mesh currents
: Write the equations for the two mesh currents. - Solve the equations and find the values of the following currents. - Build the circuit in Multisim and measure the current values.
|
|
Discuss your preferred econometric technique
: Discuss your preferred econometric technique for estimating environmental loss. Defend your choice and demonstrate your rationale in choosing this technique while offering your critique of your classmates' choices.
|