Databases Reference
In-Depth Information
Example 8.2 : The obvious greedy algorithm for the situation described in
Example 8.1 is to assign a query to the highest bidder who still has budget left.
For the data of that example, what will happen is that the first 500 “sofa” or
“chesterfield” queries will be assigned to B. At that time, B runs out of budget
and is assigned no more queries. After that, the next 1000 “chesterfield” queries
are assigned to A, and “sofa” queries get no ad and therefore earn the search
engine no money.
The worst thing that can happen is that 500 “chesterfield” queries arrive,
followed by 500 “sofa” queries. An off-line algorithm could optimally assign the
first 500 to A, earning $50, and the next 500 to B, earning $100, or a total
of $150. However, the greedy algorithm will assign the first 500 to B, earning
$100, and then has no ad for the next 500, earning nothing.
2
8.2.3
The Competitive Ratio
As we see from Example 8.2, an on-line algorithm need not give as good a result
as the best off-line algorithm for the same problem. The most we can expect is
that there will be some constant c less than 1, such that on any input, the result
of a particular on-line algorithm is at least c times the result of the optimum
off-line algorithm. The constant c, if it exists, is called the competitive ratio for
the on-line algorithm.
Example 8.3 : The greedy algorithm, on the particular data of Example 8.2,
gives a result that is 2/3 as good as that of the optimum algorithm: $100 versus
$150. That proves that the competitive ratio is no greater than 2/3. But it
could be less. The competitive ratio for an algorithm may depend on what kind
of data is allowed to be input to the algorithm. Even if we restrict inputs to
the situation described in Example 8.2, but with the bids allowed to vary, then
we can show the greedy algorithm has a competitive ratio no greater than 1/2.
Just raise the bid by A to ǫ less than 20 cents. As ǫ approaches 0, the greedy
algorithm still produces only $100, but the return from the optimum algorithm
approaches $200. We can show that it is impossible to do worse than half the
optimum in this simple case, so the competitive ratio is indeed 1/2. However,
we'll leave this sort of proof for later sections.
2
8.2.4
Exercises for Section 8.2
! Exercise 8.2.1 : A popular example of the design of an on-line algorithm to
minimize the competitive ratio is the ski-buying problem.
3
Suppose you can buy
skis for $100, or you can rent skis for $10 per day. You decide to take up skiing,
but you don't know if you will like it. You may try skiing for any number of
days and then give it up. The merit of an algorithm is the cost per day of skis,
and we must try to minimize this cost.
3
Thanks to Anna Karlin for this example.
