Question

Consider the following scenario: There are three advertisers A, B, and C A bids on query x, B bids on x and y, and C bids on x, y, and z All have budgets of $3. Given the following query stream: x x x y y y z z z What is the sequence of choices, assuming the worst case scenario, for the BALANCE algorithm?

Answer 1

Answer:

A A A B B B C C C  

Step-by-step explanation:

We have the Greedy algorithm, the solution at any time is considered an optimal algorithm.

In our case the sequence is x x x y y y z z z

In addition to the Greedy algorithm, the first advertiser chooses their choice without considering the minimum methods.

Now we must consider the worst case of greedy algorithm so we must suppose that it starts from advertiser C, then B and followed by A.

Therefore the worst option would come being:

C C C B B B, in addition that A cannot bid for any query.

Which means that the sequence of the balanced algorithm will be A A A B B B C C C