Database Reference
In-Depth Information
8.2.2
Greedy Algorithms
Many on-line algorithms are of the
greedy algorithm
type. These algorithms make their de-
cision in response to each input element by maximizing some function of the input element
and the past.
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.
□
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 sec-
tions.
□
